Potential forbidden triples implying hamiltonicity: for sufficiently large graphs

• Autorzy: Ralph J. Faudree , Ronald J. Gould , Michael S. Jacobson
• Języki publikacji: EN

Abstrakty

EN

In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with $G_i = K_{1,3}$ for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁,G₂,G₃ such that all G₁G₂G₃-free graphs are hamiltonian. In this paper we consider the question of which triples (including $K_{1,s}$, s ≥ 3) of forbidden subgraphs potentially imply all sufficiently large graphs are hamiltonian. For s ≥ 4 we characterize these families.

Słowa kluczowe

EN

hamiltonian; forbidden subgraph; claw-free; induced subgraph

Kategorie tematyczne

• 05C45: Eulerian and Hamiltonian graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2005
• Tom: 25
• Numer: 3
• Strony: 273-289

Daty

wydano

2005

otrzymano

2003-12-20

poprawiono

2005-06-14

Twórcy

autor

Ralph J. Faudree

• University of Memphis, Memphis, TN 38152, USA

autor

Ronald J. Gould

• Emory University, Atlanta, GA 30322, USA

autor

Michael S. Jacobson

• University of Colorado at Denver, Denver, CO 80217, USA

Bibliografia

• [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 $K_{1,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.

Identyfikatory

DOI

10.7151/dmgt.1281