×

Pancyclicity of Hamiltonian and highly connected graphs. (English) Zbl 1208.05071

Let be \(\kappa (G)\) the vertex connectivity and \(\alpha (G)\) the independence number of \(G\). The authors prove that if \(\kappa(G) \geqslant 600\alpha(G)\) then \(G\) is pancyclic (i.e., contains cycles of length \(\ell\), \(3 \leqslant \ell \leqslant V(G)\)). This establishes a conjecture of B. Jackson and O. Ordaz [Discrete Math. 84, No.3, 241–254 (1990; Zbl 0726.05043)] up to a constant factor.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles

Citations:

Zbl 0726.05043
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P. Allen, Minimum degree conditions for cycles, submitted for publication; P. Allen, Minimum degree conditions for cycles, submitted for publication
[2] Alon, N.; Spencer, J., The Probabilistic Method (2000), Wiley: Wiley New York
[3] Amar, D.; Fournier, I.; Germa, A., Pancyclism in Chvátal-Erdős’s graphs, Graphs Combin., 7, 101-112 (1991) · Zbl 0732.05034
[4] Bondy, J. A., Pancyclic graphs I, J. Combin. Theory Ser. B, 11, 80-84 (1971) · Zbl 0183.52301
[5] Bondy, J. A., Pancyclic graphs: Recent results, infinite and finite sets, (Colloq. Math. Soc. János Bolyai (1973), Keszthely: Keszthely Hungary), 181-187
[6] Bondy, J. A., Basic graph theory: Paths and circuits, (Handbook of Combinatorics (1995), North-Holland: North-Holland Amsterdam), 3-110 · Zbl 0849.05044
[7] Chvátal, V.; Erdős, P., A note on Hamiltonian circuits, Discrete Math., 2, 111-113 (1972) · Zbl 0233.05123
[8] Dirac, G. A., Some theorems on abstract graphs, Proc. London Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001
[9] Erdős, P., Some problems in graph theory, (Hypergraph Seminar. Hypergraph Seminar, Ohio State Univ., Columbus, Ohio, 1972. Hypergraph Seminar. Hypergraph Seminar, Ohio State Univ., Columbus, Ohio, 1972, Lecture Notes in Math., vol. 411 (1974), Springer: Springer Berlin), 187-190
[10] Erdős, P.; Faudree, R. J.; Rousseau, C. C.; Schelp, R. H., On cycle-complete graph Ramsey numbers, J. Graph Theory, 2, 53-64 (1978) · Zbl 0383.05027
[11] Flandrin, E.; Li, H.; Marczyk, A.; Wozniak, M., A note on pancyclism of highly connected graphs, Discrete Math., 286, 57-60 (2004) · Zbl 1050.05073
[12] Gould, R. J., Updating the Hamiltonian problem - A survey, J. Graph Theory, 15, 121-157 (1991) · Zbl 0746.05039
[13] Gould, R. J., Advances on the Hamiltonian problem - A survey, Graphs Combin., 19, 7-52 (2003) · Zbl 1024.05057
[14] Gould, R. J.; Haxell, P. E.; Scott, A. D., A note on cycle lengths in graphs, Graphs Combin., 18, 491-498 (2002) · Zbl 1009.05079
[15] Jackson, B.; Ordaz, O., Chvátal-Erdős conditions for paths and cycles in graphs and digraphs: A survey, Discrete Math., 84, 241-254 (1990) · Zbl 0726.05043
[16] Lou, D., The Chvátal-Erdős condition for cycles in triangle-free graphs, Discrete Math., 152, 253-257 (1996) · Zbl 0857.05056
[17] Sudakov, B.; Verstraëte, J., Cycle lengths in sparse graphs, Combinatorica, 28, 357-372 (2008) · Zbl 1174.05065
[18] Verstraëte, J., On arithmetic progressions of cycle lengths in graphs, Combin. Probab. Comput., 9, 369-373 (2000) · Zbl 0978.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.