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