DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 24(1) (2004) 47-54
DOI: https://doi.org/10.7151/dmgt.1212

FORBIDDEN TRIPLES IMPLYING HAMILTONICITY: FOR ALL 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 Denver, CO 80217, USA

Abstract

In [2], Brousek characterizes all triples of graphs, G1,G2, G3, with Gi = K1,3 for some i = 1, 2, or 3, such that all G1 G2 G3-free graphs contain a hamiltonian cycle. In [6], 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 G1, G2, G3-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G1, G2, G3 with none being K1,3, such that all G1 G2G3-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G1, G2, G3 such that all G1 G2 G3-free graphs are hamiltonian.

Keywords: hamiltonian, induced subgraph, forbidden subgraphs.

2000 Mathematics Subject Classification: primary: 05C, secondary: 05C35, 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] 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.

Received 15 March 2001
Revised 25 April 2003

Close