Skip to main content
Article
Pan-H-Linked Graphs
Graphs and Combinatorics (2010)
• , University of Colorado
• , Georgia Southern University
• , Samford University
Abstract
Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n0(H) isolated vertices and n1(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H and δ(G)≥ n+m−k+n1(H)+2n0(H)/2, then G contains a spanning H-subdivision with the same ground set as H . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3 with δ(G)≥n/2 , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition δ(G)≥n/2 then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165–182, 2007) in a similar manner. An H-subdivision H in G is 1-extendible if there exists an H-subdivision H∗ with the same ground set as H and |H∗|=|H|+1 . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that δ(G)≥n+m−k+n1(H)+2n0(H)/2 , then G is pan-H-linked. This result is sharp.
Keywords
• H-subdivision,
• Pan-H-linked,
• Pancyclic,
• Panconnected
Disciplines
Publication Date
March, 2010
DOI
10.1007/s00373-010-0911-3
Citation Information
Micheal Ferrara, Colton Magnant and Jeffery Powell. "Pan-H-Linked Graphs" Graphs and Combinatorics Vol. 26 Iss. 2 (2010) p. 225 - 242 ISSN: 1435-5914
Available at: http://works.bepress.com/colton_magnant/7/