Abstract
Given a fixed multigraph H with V(H) = {h1,..., hm}, we say that a graph G is H-linked if for every choice of m vertices v 1,..., vm in G, there exists a subdivision of H in G such that for every i, vi, is the branch vertex representing h i. This generalizes the notion of k-linked graphs (as well as some other notions). For a family H of graphs, a graph G is H-linked if G is H-linked for every H ∈ H. In this article, we estimate the minimum integer r=r(n,k,d) such that each n-vertex graph with σ2(G)≥r is H-linked, where H is the family of simple graphs with k edges and minimum degree at least d≥2.
Original language | English (US) |
---|---|
Pages (from-to) | 14-26 |
Number of pages | 13 |
Journal | Journal of Graph Theory |
Volume | 58 |
Issue number | 1 |
DOIs | |
State | Published - May 2008 |
Keywords
- H-linked
- Ore-type degree condition
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics