DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 30(2) (2010) 245-256
DOI: 10.7151/dmgt.1490

CHVÁTAL-ERDÖS TYPE THEOREMS

Jill R. Faudree

University of Alaska at Fairbanks
Fairbanks, AK 99775-6660, USA

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 Denver
Denver, CO 80217, USA

Colton Magnant

Lehigh University
Bethlehem, PA 18015, USA

Abstract

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k2-k)/(k+1), and δ(G) ≥ α(G)+k-2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k2+1, δ(G) > (n+k2-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k2-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.

Keywords: Hamiltonian, Hamiltonian-connected, Chvátal-Erdös condition, independence number.

2010 Mathematics Subject Classification: Primary: 05C45;
Secondary: 05C35.

References

[1] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman and Hall, London, 1996).
[2] V. Chvátal and P. Erdös, A note on Hamiltonian circuits, Discrete Math 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9.
[3] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69.
[4] H. Enomoto, Long paths and large cycles in finite graphs, J. Graph Theory 8 (1984) 287-301, doi: 10.1002/jgt.3190080209.
[5] P. Fraisse, Dλ-cycles and their applications for hamiltonian cycles, Thése de Doctorat d'état (Université de Paris-Sud, 1986).
[6] K. Ota, Cycles through prescribed vertices with large degree sum, Discrete Math. 145 (1995) 201-210, doi: 10.1016/0012-365X(94)00036-I.

Received 20 January 2009
Revised 25 June 2009
Accepted 25 June 2009