Longest Cycles in 2-Connected Graphs with Prescribed Maximum Degree

Bondy, J. A. ; Entringer, R. C.

Canadian journal of mathematics, Tome 32 (1980) no. 6, pp. 1325-1332

Résumé

The relationship between the lengths of cycles in a graph and the degrees of its vertices was first studied in a general context by G. A. Dirac. In [5], he proved that every 2-connected simple graph on n vertices with minimum degree d contains a cycle of length at least min{2d, n};. Dirac's theorem was subsequently strengthened in various directions in [7], [6], [13], [12], [2], [1], [11], [8], [14], [15] and [16].Our aim here is to investigate another aspect of this relationship, namely how the lengths of the cycles in a 2-connected graph depend on the maximum degree. Let us denote by ƒ(n, d) the largest integer k such that every 2-connected simple graph on n vertices with maximum degree d contains a cycle of length at least k. We prove in Section 2 that, for d ≧ 3 and n ≧ d + 2,

Détail

DOI : 10.4153/CJM-1980-102-7

Bibliographie

[1] 1. Bermond, J. C., On Hamiltonian walks, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975). Congressus Numerantium, Utilitas Math. Winnipeg, Man. 15 (1976), 41–51. Google Scholar

[2] 2. Bondy, J. A., Large cycles in graphs, Discrete Math. 1.2 (1971), 121–132. Google Scholar

[3] 3. Bondy, J. A., Hamilton cycles in graphs and digraphs, Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Florida (1978), Utilitas Math. 21 (1978), 3–28. Google Scholar

[4] 4. Bondy, J. A. and Simonovits, M., Longest cycles in 3-connected S-regular graphs, Can. J. Math., to appear. Google Scholar | DOI

[5] 5. Dirac, G. A., Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952), 69–81. Google Scholar

[6] 6. Dirac, G. A., Palhs and circuits in graphs: extreme cases, Acta Math. Acad. Sci. Hungar. 10 (1959), 357–362. Google Scholar

[7] 7. Erdös, P. and Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356. Google Scholar

[8] 8. Grötschel, M., Graphs with cycles containing given paths, Ann. of Discrete Math. 1 (1977), 233–245. Google Scholar

[9] 9. Jackson, B., Hamilton cycles in regular 2-connected graphs, J. Combinatorial Theory Ser. B. 29 (1980), 47–67. Google Scholar

[10] 10. Lang, R. and Walther, H., Über längste Kreise in regulären Graphen, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967). Teubner, Leipzig (1968), 91–98. Google Scholar

[11] 11. Linial, N., A lower bound for the circumference of a graph, Discrete Math. 15.3 (1976), 297–300. Google Scholar

[12] 12. Ore, O., On a graph theorem by Dirac, J. Combinatorial Theory 2 (1967), 383–392. Google Scholar

[13] 13. Pósa, L., On the circuits of finite graphs, (Russian summary) Magyar Tud. Akad. Mat. Kutato Int. Közl. 8 (1963), 355–361. Google Scholar

[14] 14. Voss, H.-J., Maximal circuits and paths in graphs: extreme cases, Combinatorics (Proc. Conf. Keszthely, 1976), Colloq. Math. Soc. János Bolyai (North-Holland Publishing Company, New York) 18 (1978), 1099–1122. Google Scholar

[15] 15. Voss, H.-J., Bridges of longest circuits and of longest paths in graphs, Beiträge zur Graphentheorie und deren Anwendungen (Intern. Kolloquium, Oberhof, 1977), 275–286. Google Scholar

[16] 16. Voss, H.-J. and Zuluaga, C., Maximale gerade und ungerade Kreise in Graphen, I, Wiss. Z. Techn. Hochsch. Ilmenau 23A (1977), 57–70. Google Scholar