Back to Search
Start Over
A Strengthening of Erd\H{o}s-Gallai Theorem and Proof of Woodall's Conjecture
- Source :
- Journal of Combinatorial Theory, Series B Volume 146, January 2021, Pages 76--95
- Publication Year :
- 2020
-
Abstract
- 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 well-known theorem due to Erd\H{o}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 $2k$ if it has at least $\frac{n}{2}+k$ vertices of degree at least $k$. This confirms a 1975 conjecture made by Woodall. As another applications, we obtain some results which generalize previous theorems of Dirac, Erd\H{o}s-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Koml\'{o}s-S\'{o}s Conjecture which was verified by Bazgan et al. and of 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.<br />Comment: 16 pages, to appear in Journal of Combinatorial Theory, Series B
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- Journal of Combinatorial Theory, Series B Volume 146, January 2021, Pages 76--95
- Publication Type :
- Report
- Accession number :
- edsarx.2002.04198
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.jctb.2020.08.003