Chvátal-Erdös type theorems

• Autorzy: Jill R. Faudree , Ralph J. Faudree , Ronald J. Gould , Michael S. Jacobson , Colton Magnant
• Języki publikacji: EN

Abstrakty

EN

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+k²-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) ≥ 4k²+1, δ(G) > (n+k²-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+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.

Słowa kluczowe

EN

Hamiltonian; Hamiltonian-connected; Chvátal-Erdös condition; independence number

Kategorie tematyczne

• 05C35: Extremal problems
• 05C45: Eulerian and Hamiltonian graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2010
• Tom: 30
• Numer: 2
• Strony: 245-256

Daty

wydano

2010

otrzymano

2009-01-20

poprawiono

2009-06-25

zaakceptowano

2009-06-25

Twórcy

autor

Jill R. Faudree

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

autor

Ralph J. Faudree

• University of Memphis, Memphis, TN 38152, USA

autor

Ronald J. Gould

• Emory University, Atlanta, GA 30322, USA

autor

Michael S. Jacobson

• University of Colorado Denver, Denver, CO 80217, USA

autor

Colton Magnant

• Lehigh University, Bethlehem, PA 18015, USA

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1490