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

[BIBTex] [PDF] [PS]

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