Abstract
For a fixed multigraph H with vertices w1, ..., wm, a graph G is H-linked if for every choice of vertices v1, ..., vm in G, there exists a subdivision of H in G such that vi is the branch vertex representing wi (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs. Given a connected multigraph H with k edges and minimum degree at least two and n ≥ 7.5 k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D (H, n) appears to equal the least integer d′ such that every n-vertex graph with minimum degree at least d′ is b (H)-connected, where b (H) is the maximum number of edges in a bipartite subgraph of H.
Original language | English (US) |
---|---|
Pages (from-to) | 1542-1548 |
Number of pages | 7 |
Journal | Discrete Applied Mathematics |
Volume | 156 |
Issue number | 9 |
DOIs | |
State | Published - May 1 2008 |
Keywords
- Degree conditions
- Extremal graph problems
- H-linked graphs
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics