Geodesic
Chvátal-Erdos condition and pancyclism
Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 2, pp. 335-342

Voir la notice de l'article provenant de la source Library of Science

The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.
Keywords: hamiltonian graphs, pancyclic graphs, cycles, connectivity, stability number 
@article{DMGT_2006_26_2_a13,
     author = {Flandrin, Evelyne and Li, Hao and Marczyk, Antoni and Schiermeyer, Ingo and Wo\'zniak, Mariusz},
     title = {Chv\'atal-Erdos condition and pancyclism},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {335--342},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2006_26_2_a13/}
}
TY  - JOUR
AU  - Flandrin, Evelyne
AU  - Li, Hao
AU  - Marczyk, Antoni
AU  - Schiermeyer, Ingo
AU  - Woźniak, Mariusz
TI  - Chvátal-Erdos condition and pancyclism
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2006
SP  - 335
EP  - 342
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2006_26_2_a13/
LA  - en
ID  - DMGT_2006_26_2_a13
ER  - 
%0 Journal Article
%A Flandrin, Evelyne
%A Li, Hao
%A Marczyk, Antoni
%A Schiermeyer, Ingo
%A Woźniak, Mariusz
%T Chvátal-Erdos condition and pancyclism
%J Discussiones Mathematicae. Graph Theory
%D 2006
%P 335-342
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2006_26_2_a13/
%G en
%F DMGT_2006_26_2_a13
Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Schiermeyer, Ingo; Woźniak, Mariusz. Chvátal-Erdos condition and pancyclism. Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 2, pp. 335-342. http://geodesic.mathdoc.fr/item/DMGT_2006_26_2_a13/