×

A strengthening of Erdős-Gallai theorem and proof of Woodall’s conjecture. (English) Zbl 1457.05057

Summary: For a 2-connected graph \(G\) on \(n\) vertices and two vertices \(x, y \in V(G)\), we prove that there is an \((x, y)\)-path of length at least \(k\), if there are at least \(\frac{ n - 1}{ 2}\) vertices in \(V(G) \backslash \{x, y \}\) of degree at least \(k\). This strengthens a celebrated theorem due to P. Erdős and T. Gallai [Acta Math. Acad. Sci. Hung. 10, 337–356 (1959; Zbl 0090.39401)]. As the first application of this result, we show that a 2-connected graph with \(n\) vertices contains a cycle of length at least \(2k\), if it has at least \(\frac{ n}{ 2} + k\) vertices of degree at least \(k\). This confirms a 1975 conjecture made by D. R. Woodall [Stud. Sci. Math. Hung. 10, 103–109 (1977; Zbl 0361.05042)]. As other applications, we obtain some results which generalize previous theorems of G. A. Dirac [Proc. Lond. Math. Soc. (3) 2, 69–81 (1952; Zbl 0047.17001)], Erdős and Gallai [loc. cit.], J. A. Bondy [Discrete Math. 1, 121–132 (1971; Zbl 0224.05120)], and J. Fujisawa et al. [J. Graph Theory 49, No. 2, 93–103 (2005; Zbl 1064.05093)], present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by C. Bazgan et al. [J. Graph Theory 34, No. 4, 269–276 (2000; Zbl 0958.05028)] and a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by I. Fournier and P. Fraisse [J. Comb. Theory, Ser. B 39, 17–26 (1985; Zbl 0576.05035)], and make progress on a conjecture of J. C. Bermond [in: Proceedings of the 5th British combinatorial conference 1975. University of Aberdeen, Aberdeen, July 14–18, 1975. Winnipeg: Utilitas Mathematica Publishing Inc. 41–51 (1976; Zbl 0329.05113)].

MSC:

05C38 Paths and cycles
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., The longest cycle of a graph with a large minimal degree, J. Graph Theory, 10, 1, 123-127 (1986) · Zbl 0592.05042
[2] Bazgan, C.; Li, H.; Woźniak, M., On the Loebl-Komlós-Sós conjecture, J. Graph Theory, 34, 4, 269-276 (2000) · Zbl 0958.05028
[3] Bermond, J. C., On Hamiltonian walks, Congr. Numer., 15, 41-51 (1976) · Zbl 0329.05113
[4] Bollobás, B., Extremal Graph Theory, London Mathematical Society Monographs, vol. 11 (1978), Academic Press: Academic Press New York, London · Zbl 0419.05031
[5] Bondy, J. A., Large cycles in graphs, Discrete Math., 1, 2, 121-132 (1971/1972) · Zbl 0224.05120
[6] Bondy, J. A., Integrity in graph theory, (Chartrand, G., The Theory and Applications of Graphs: Proc. 4th Internat. Graph Theory Conf. (1981), Wiley: Wiley New York), 117-125 · Zbl 0468.05045
[7] Bondy, J. A.; Jackson, B., Long paths between specified vertices of a block, Ann. Discrete Math., 27, 195-200 (1985) · Zbl 0581.05033
[8] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan Press: Macmillan Press New York · Zbl 1226.05083
[9] Dean, N.; Fraisse, P., A degree condition for the circumference of a graph, J. Graph Theory, 13, 3, 331-334 (1989) · Zbl 0679.05044
[10] Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001
[11] Erdős, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hung., 10, 337-356 (1959) · Zbl 0090.39401
[12] Fan, G., Subgraph coverings and edge switchings, J. Comb. Theory, Ser. B, 84, 1, 54-83 (2002) · Zbl 1031.05104
[13] Fournier, I.; Fraisse, P., On a conjecture of Bondy, J. Comb. Theory, Ser. B, 39, 1, 17-26 (1985) · Zbl 0576.05035
[14] Fujisawa, J.; Yoshimoto, K.; Zhang, S., Heavy cycles passing through some specified vertices in weighted graphs, J. Graph Theory, 49, 2, 93-103 (2005) · Zbl 1064.05093
[15] Häggkvist, R.; Jackson, B., A note on maximal cycles in 2-connected graphs, Ann. Discrete Math., 27, 205-208 (1985) · Zbl 0573.05038
[16] Kelmans, A. K., On graphs with randomly deleted edges, Acta Math. Acad. Sci. Hung., 37, 77-88 (1981) · Zbl 0503.05056
[17] D. Li, H. Li, On longest cycles in graphs, Rapport de recherche no 1160, LRI, URA 410 du CNRS, Bat. 490, Univ. de Paris sud, 91405-Orsay, France. · Zbl 0774.05054
[18] Li, H., On a conjecture of Woodall, J. Comb. Theory, Ser. B, 86, 1, 172-185 (2002) · Zbl 1023.05086
[19] H. Li, Woodall’s conjecture on long cycles, Rapport de recherche no 1296, LRI, UMR 8623 CNRS-UPS, Bat. 490, Univ. de Paris sud, 91405-Orsay, France.
[20] Li, H., Generalizations of Dirac’s theorem in Hamiltonian graph theory-a survey, Discrete Math., 313, 19, 2034-2053 (2013) · Zbl 1277.05100
[21] Locke, S. C., Relative lengths of paths and cycles in k-connected graphs, J. Comb. Theory, Ser. B, 32, 2, 206-222 (1982) · Zbl 0492.05048
[22] Ma, J.; Ning, B., Stability results on the circumference of a graph, Combinatorica, 40, 1, 105-147 (2020) · Zbl 1449.05163
[23] Tutte, W. T., Connectivity in Graphs, Mathematical Expositions, vol. 15 (1966), University of Toronto Press: University of Toronto Press Toronto, Ont., Oxford University Press, London · Zbl 0146.45603
[24] Woodall, D. R., Maximal circuits of graphs II, Studia Sci. Math. Hung., 10, 103-109 (1975) · Zbl 0361.05042
[25] H. Wu, Private communication with the second author.
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.