Skip to main content
Article
Chvátal-Erdös Type Theorems
Discussiones Mathematicae Graph Theory (2010)
  • Ralph J. Faudree, University of Memphis
  • Jill R. Faudree
  • Ronald J. Gould, Emory University
  • Michael S. Jacobson
  • Colton Magnant, Georgia Southern 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
Disciplines
Publication Date
2010
Publisher Statement
Article under the Creative Commons Attribution-NonCommercial-NoDerivs license. Article obtained from the Discussiones Mathematicae Graph Theory.
Citation Information
Ralph J. Faudree, Jill R. Faudree, Ronald J. Gould, Michael S. Jacobson, and Colton Magnant. "Chvátal-Erdös Type Theorems" Discussiones Mathematicae Graph Theory 30.2 (2010): 245-256.
doi:10.7151/dmgt.1490
Available at: http://works.bepress.com/colton_magnant/6