PDF

Discussiones Mathematicae Graph Theory 26(2) (2006) 335-342
DOI: https://doi.org/10.7151/dmgt.1324

CHVÁTAL-ERDOS CONDITION AND PANCYCLISM

Evelyne Flandrin,^*, Hao Li,^*, Antoni Marczyk^f, Ingo Schiermeyer^f and Mariusz Woźniak^f

^*LRI, UMR 8623, Bât. 490, Université de Paris-Sud
91405 Orsay, France

^fAGH University of Science and Technology
Faculty of Applied Mathematics
Al. Mickiewicza 30, 30-059 Kraków, Poland

^fFakultät für Mathematik und Informatik
Technische Universität Bergakademie Freiberg
D-09596 Freiberg, Germany

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.

Keywords: hamiltonian graphs, pancyclic graphs, cycles, connectivity, stability number.

2000 Mathematics Subject Classification: 05C38, 05C45.

References

[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:3<141::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.

Received 17 February 2005
Revised 21 November 2005