Geodesic
Chvátal-Erdös type theorems
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 245-256
Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: Hamiltonian, Hamiltonian-connected, Chvátal-Erdös condition, independence number 
@article{DMGT_2010_30_2_a4,
     author = {Faudree, Jill and Faudree, Ralph and Gould, Ronald and Jacobson, Michael and Magnant, Colton},
     title = {Chv\'atal-Erd\"os type theorems},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {245--256},
     year = {2010},
     volume = {30},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a4/}
}
TY  - JOUR
AU  - Faudree, Jill
AU  - Faudree, Ralph
AU  - Gould, Ronald
AU  - Jacobson, Michael
AU  - Magnant, Colton
TI  - Chvátal-Erdös type theorems
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 245
EP  - 256
VL  - 30
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a4/
LA  - en
ID  - DMGT_2010_30_2_a4
ER  - 
%0 Journal Article
%A Faudree, Jill
%A Faudree, Ralph
%A Gould, Ronald
%A Jacobson, Michael
%A Magnant, Colton
%T Chvátal-Erdös type theorems
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 245-256
%V 30
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a4/
%G en
%F DMGT_2010_30_2_a4
Faudree, Jill; Faudree, Ralph; Gould, Ronald; Jacobson, Michael; Magnant, Colton. Chvátal-Erdös type theorems. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 245-256. http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a4/

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