# Chvátal-Erdös type theorems

Jill R. Faudree; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Colton Magnant

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 2, page 245-256
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJill R. Faudree, et al. "Chvátal-Erdös type theorems." Discussiones Mathematicae Graph Theory 30.2 (2010): 245-256. <http://eudml.org/doc/270915>.

@article{JillR2010,

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+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.},

author = {Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Colton Magnant},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Hamiltonian; Hamiltonian-connected; Chvátal-Erdös condition; independence number; Chvátal-Erdős condition},

language = {eng},

number = {2},

pages = {245-256},

title = {Chvátal-Erdös type theorems},

url = {http://eudml.org/doc/270915},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Jill R. Faudree

AU - Ralph J. Faudree

AU - Ronald J. Gould

AU - Michael S. Jacobson

AU - Colton Magnant

TI - Chvátal-Erdös type theorems

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 2

SP - 245

EP - 256

AB - 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.

LA - eng

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

UR - http://eudml.org/doc/270915

ER -

## References

top- [1] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman and Hall, London, 1996). Zbl0890.05001
- [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. Zbl0233.05123
- [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. Zbl0047.17001
- [4] H. Enomoto, Long paths and large cycles in finite graphs, J. Graph Theory 8 (1984) 287-301, doi: 10.1002/jgt.3190080209. Zbl0544.05044
- [5] P. Fraisse, ${D}_{\lambda}$-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. Zbl0838.05071

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.