Forbidden triples implying Hamiltonicity: for all graphs
Ralph J. Faudree ; Ronald J. Gould ; Michael S. Jacobson
Discussiones Mathematicae Graph Theory, Tome 24 (2004), p. 47-54 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with Gi=K1,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 K1,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 K1,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.

Publié le : 2004-01-01
EUDML-ID : urn:eudml:doc:270547 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1212,
     author = {Ralph J. Faudree and Ronald J. Gould and Michael S. Jacobson},
     title = {Forbidden triples implying Hamiltonicity: for all graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {24},
     year = {2004},
     pages = {47-54},
     zbl = {1060.05063},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1212}
}

Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson. Forbidden triples implying Hamiltonicity: for all graphs. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 47-54. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1212/

[000] [1] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity (Ph.D. Thesis, Memphis State University, 1991).

[001] [2] J. Brousek, Forbidden Triples and Hamiltonicity, Discrete Math. 251 (2002) 71-76, doi: 10.1016/S0012-365X(01)00326-0. | Zbl 1002.05044

[002] [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (3rd Edition, Chapman & Hall, 1996).

[003] [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. | Zbl 0879.05050

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

[005] [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. | Zbl 0990.05091