Discussiones Mathematicae Graph Theory 30(2) (2010)
245-256
DOI: https://doi.org/10.7151/dmgt.1490
CHVÁTAL-ERDÖS TYPE THEOREMS
Jill R. Faudree
University of Alaska at Fairbanks |
Ralph J. Faudree
University of Memphis |
Ronald J. Gould
Emory University |
Michael S. Jacobson
University of Colorado Denver |
Colton Magnant
Lehigh University |
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
Close