Geodesic
Forbidden triples implying Hamiltonicity: for all graphs
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 1, pp. 47-54.

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

In [2], Brousek characterizes all triples of 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 [6], 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 this paper, a characterization will be 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.
Keywords: hamiltonian, induced subgraph, forbidden subgraphs 
@article{DMGT_2004_24_1_a3,
     author = {Faudree, Ralph and Gould, Ronald and Jacobson, Michael},
     title = {Forbidden triples implying {Hamiltonicity:} for all graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {47--54},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a3/}
}
TY  - JOUR
AU  - Faudree, Ralph
AU  - Gould, Ronald
AU  - Jacobson, Michael
TI  - Forbidden triples implying Hamiltonicity: for all graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 47
EP  - 54
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a3/
LA  - en
ID  - DMGT_2004_24_1_a3
ER  - 
%0 Journal Article
%A Faudree, Ralph
%A Gould, Ronald
%A Jacobson, Michael
%T Forbidden triples implying Hamiltonicity: for all graphs
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 47-54
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a3/
%G en
%F DMGT_2004_24_1_a3
Faudree, Ralph; Gould, Ronald; Jacobson, Michael. Forbidden triples implying Hamiltonicity: for all graphs. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 1, pp. 47-54. http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a3/

[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] G. Chartrand and L. Lesniak, Graphs Digraphs (3rd Edition, Chapman Hall, 1996).

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

[5] R.J. Faudree, R.J. Gould and M.S. Jacobson, Potential Forbidden Triples Implying Hamiltonicity: For Sufficiently Large Graphs, preprint.

[6] R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak, Characterizing Forbidden Clawless Triples for Hamiltonian Graphs, Discrete Math. 249 (2002) 71-81, doi: 10.1016/S0012-365X(01)00235-7.