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

Abstract

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

How to cite

top

Evelyne 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. [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. [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. [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. [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. [5] J.A. Bondy and U.S.R. Murty, Graphs Theory with Applications (Macmillan. London, 1976). Zbl1226.05083
  6. [6] S. Brandt, private communication. 
  7. [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. [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. [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. [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. [11] P. Erdős, Some problems in Graph Theory, in: Lecture Notes Math. 411 (1974) 187-190. 
  12. [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. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.