PDF
POTENTIAL FORBIDDEN TRIPLES IMPLYING HAMILTONICITY:
Discussiones Mathematicae Graph Theory 25(3) (2005)
273-289
DOI: https://doi.org/10.7151/dmgt.1281
POTENTIAL FORBIDDEN TRIPLES IMPLYING HAMILTONICITY:
FOR SUFFICIENTLY LARGE GRAPHS
Ralph J. Faudree
University of Memphis, Memphis, TN 38152, USA | Ronald J. Gould
Emory University, Atlanta, GA 30322, USA |
Michael S. Jacobson
University of Colorado at Denver
|
Abstract
In [1], Brousek characterizes all triples of connected graphs, G1, G2,G3, with Gi = K1,3 for some i = 1,2, or 3, such that all G1G2 G3-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G1,G2,G3, none of which is a K1,s, s ≥ 3 such that G1G2G3-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G1,G2,G3 with none being K1,3, such that all G1G2G3-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G1,G2,G3 such that all G1G2G3-free graphs are hamiltonian. In this paper we consider the question of which triples (including K1,s, s ≥ 3) of forbidden subgraphs potentially imply all sufficiently large graphs are hamiltonian. For s ≥ 4 we characterize these families.Keywords: hamiltonian, forbidden subgraph, claw-free, induced subgraph.
2000 Mathematics Subject Classification: 05C45.
References
[1] | P. Bedrossian, Forbidden subgraph and minimum degree conditions for hamiltonicity (Ph.D. Thesis, Memphis State University, 1991). |
[2] | J. Brousek, Forbidden triples and hamiltonicity, Discrete Math. 251 (2002) 71-76, doi: 10.1016/S0012-365X(01)00326-0. |
[3] | J. Brousek, Z. Ryjácek and I. Schiermeyer, Forbidden subgraphs, stability and hamiltonicity, 18th British Combinatorial Conference (London, 1997), Discrete Math. 197/198 (1999) 143-155, doi: 10.1016/S0012-365X(98)00229-5. |
[4] | G. Chartrand and L. Lesniak, Graphs & Digraphs (3rd Edition, Chapman & Hall, 1996). |
[5] | R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for hamiltonian properties, Discrete Math. 173 (1997) 45-60, doi: 10.1016/S0012-365X(96)00147-1. |
[6] | R.J. Faudree, R.J. Gould and M.S. Jacobson, Forbidden triples implying hamiltonicity: for all graphs, Discuss. Math. Graph Theory 24 (2004) 47-54, doi: 10.7151/dmgt.1212. |
[7] | R.J. Faudree, R.J. Gould and M.S. Jacobson, Forbidden triples including K1,3 implying hamiltonicity: for sufficiently large graphs, preprint. |
[8] | R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak, Characterizing forbidden clawless triples implying hamiltonian graphs, Discrete Math. 249 (2002) 71-81, doi: 10.1016/S0012-365X(01)00235-7. |
Received 20 December 2003
Revised 14 June 2005
Close