Abstract
For a 2-connected graph on vertices and two vertices , we prove that there is an -path of length at least if there are at least vertices in of degree at least . This strengthens a well-known theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with vertices contains a cycle of length at least if it has at least vertices of degree at least . This confirms a 1975 conjecture made by Woodall. As another 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 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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.