Article

Pan-H-Linked Graphs

Graphs and Combinatorics
(2010)
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/