Back to Search
Start Over
A strengthening of Erdős-Gallai Theorem and proof of Woodall's conjecture.
- Source :
-
Journal of Combinatorial Theory - Series B . Jan2021, Vol. 146, p76-95. 20p. - Publication Year :
- 2021
-
Abstract
- For a 2-connected graph G on n vertices and two vertices x , y ∈ V (G) , we prove that there is an (x , y) -path of length at least k , if there are at least n − 1 2 vertices in V (G) \ { x , y } of degree at least k. This strengthens a celebrated theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with n vertices contains a cycle of length at least 2 k , if it has at least n 2 + k vertices of degree at least k. This confirms a 1975 conjecture made by Woodall. As other applications, we obtain some results which generalize previous theorems of Dirac, Erdős-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by Bazgan et al. and a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond. [ABSTRACT FROM AUTHOR]
- Subjects :
- *LOGICAL prediction
*EVIDENCE
*PATHS & cycles in graph theory
Subjects
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 146
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 147116842
- Full Text :
- https://doi.org/10.1016/j.jctb.2020.08.003