# Chvátal-Erdos condition and pancyclism

Evelyne Flandrin; Hao Li; Antoni Marczyk; Ingo Schiermeyer; Mariusz Woźniak

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 2, page 335-342
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topEvelyne Flandrin, et al. "Chvátal-Erdos condition and pancyclism." Discussiones Mathematicae Graph Theory 26.2 (2006): 335-342. <http://eudml.org/doc/270734>.

@article{EvelyneFlandrin2006,

abstract = {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.},

author = {Evelyne Flandrin, Hao Li, Antoni Marczyk, Ingo Schiermeyer, Mariusz Woźniak},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hamiltonian graphs; pancyclic graphs; cycles; connectivity; stability number; connectvity},

language = {eng},

number = {2},

pages = {335-342},

title = {Chvátal-Erdos condition and pancyclism},

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

volume = {26},

year = {2006},

}

TY - JOUR

AU - Evelyne Flandrin

AU - Hao Li

AU - Antoni Marczyk

AU - Ingo Schiermeyer

AU - Mariusz Woźniak

TI - Chvátal-Erdos condition and pancyclism

JO - Discussiones Mathematicae Graph Theory

PY - 2006

VL - 26

IS - 2

SP - 335

EP - 342

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

LA - eng

KW - hamiltonian graphs; pancyclic graphs; cycles; connectivity; stability number; connectvity

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

ER -

## References

top- [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. Zbl0732.05034
- [2] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5. Zbl0183.52301
- [3] J.A. Bondy, Pancyclic graphs, in: Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (1971) 167-172. Zbl0291.05109
- [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. Zbl0248.05127
- [5] J.A. Bondy and U.S.R. Murty, Graphs Theory with Applications (Macmillan. London, 1976). Zbl1226.05083
- [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:3<141::AID-JGT3>3.0.CO;2-O Zbl0927.05045
- [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. Zbl0707.05029
- [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. Zbl0144.45401
- [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. Zbl0726.05043
- [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. Zbl0857.05056
- [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. Zbl55.0032.04
- [16] S. Zhang, Pancyclism and bipancyclism of hamiltonian graphs, J. Combin. Theory (B) 60 (1994) 159-168, doi: 10.1006/jctb.1994.1010. Zbl0795.05086

## NotesEmbed ?

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