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/

[1] D. Amar, I. Fournier and A. Germa, Pancyclism in Chvátal-Erdős graphs, Graphs Combin. 7 (1991) 101-112, doi: 10.1007/BF01788136.

[2] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.

[3] J.A. Bondy, Pancyclic graphs, in: Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (1971) 167-172.

[4] J.A. Bondy and P. Erdős, Ramsey numbers for cycles in graphs, J. Combin. Theory (B) 14 (1973) 46-54, doi: 10.1016/S0095-8956(73)80005-X.

[5] J.A. Bondy and U.S.R. Murty, Graphs Theory with Applications (Macmillan. London, 1976).

[6] S. Brandt, private communication.

[7] S. Brandt, R. Faudree and W. Goddard, Weakly pancyclic graphs, J. Graph Theory 27 (1998) 141-176, doi: 10.1002/(SICI)1097-0118(199803)27:3141::AID-JGT3>3.0.CO;2-O

[8] V. Chvátal, P. Erdős, A note on Hamilton circuits, Discrete Math. 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9.

[9] N. Chakroun and D. Sotteau, Chvátal-Erdős theorem for digraphs, in: Cycles and Rays (Montreal, 1987) (Kluwer, Dordrecht, 1990) 75-86.

[10] P. Erdős, On the construction of certain graphs, J. Combin. Theory 1 (1966) 149-152, doi: 10.1016/S0021-9800(66)80011-X.

[11] P. Erdős, Some problems in Graph Theory, in: Lecture Notes Math. 411 (1974) 187-190.

[12] B. Jackson and O. Ordaz, Chvátal-Erdős condition for path and cycles in graphs and digraphs. A survey, Discrete Math. 84 (1990) 241-254, doi: 10.1016/0012-365X(90)90130-A.

[13] D. Lou, The Chvátal-Erdős condition for cycles in triangle-free graphs, Discrete Math. 152 (1996) 253-257, doi: 10.1016/0012-365X(96)80461-4.

[14] A. Marczyk and J-F. Saclé, On the Jackson-Ordaz conjecture for graphs with the stability number four (Rapport de Recherche 1287, Université de Paris-Sud, Centre d'Orsay, 2001).

[15] F.P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc. 30 (1930) 264-286, doi: 10.1112/plms/s2-30.1.264.

[16] S. Zhang, Pancyclism and bipancyclism of hamiltonian graphs, J. Combin. Theory (B) 60 (1994) 159-168, doi: 10.1006/jctb.1994.1010.