Abstract
Given a fixed multigraph H, possibly containing loops, with V(H) = {h 1,..., h m}, we say that a graph G is H-linked if for every choice of m vertices v 1,...,v m in G, there exists a subdivision of H in G such that V i is the branch vertex representing h i (for all i). This generalizes the concept of k-linked graphs (as well as a number of other well-known path or cycle properties). In this paper we determine a sharp lower bound on δ(G) (which depends upon H) such that each graph G on at least 10(|V(H)| + |E(H)|) vertices satisfying this bound is H-linked.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 829-840 |
| Number of pages | 12 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 20 |
| Issue number | 4 |
| DOIs | |
| State | Published - 2007 |
Keywords
- Connectivity
- H-linked
- Minimum degree
- k-linked
ASJC Scopus subject areas
- General Mathematics