Geodesic
Potential forbidden triples implying hamiltonicity: for sufficiently large graphs
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 273-289.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: hamiltonian, forbidden subgraph, claw-free, induced subgraph 
@article{DMGT_2005_25_3_a6,
     author = {Faudree, Ralph and Gould, Ronald and Jacobson, Michael},
     title = {Potential forbidden triples implying hamiltonicity: for sufficiently large graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {273--289},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a6/}
}
TY  - JOUR
AU  - Faudree, Ralph
AU  - Gould, Ronald
AU  - Jacobson, Michael
TI  - Potential forbidden triples implying hamiltonicity: for sufficiently large graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 273
EP  - 289
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a6/
LA  - en
ID  - DMGT_2005_25_3_a6
ER  - 
%0 Journal Article
%A Faudree, Ralph
%A Gould, Ronald
%A Jacobson, Michael
%T Potential forbidden triples implying hamiltonicity: for sufficiently large graphs
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 273-289
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a6/
%G en
%F DMGT_2005_25_3_a6
Faudree, Ralph; Gould, Ronald; Jacobson, Michael. Potential forbidden triples implying hamiltonicity: for sufficiently large graphs. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 273-289. http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a6/

[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.