.For an integer \(α\) and a graph \(G\), the \(α\)-disintegration of \(G\) is the graph obtained from \(G\) by recursively deleting vertices of degree at most \(α\) until the resulting graph has no such vertex. Pósa proved that if a 2-connected graph contains a path on \(m≥ k\) vertices with end-vertices in its \( (k-1)/2\)-disintegration, then \(G\) contains a cycle of length at least \(k\). We prove that if a 2-connected graph contains a path on \(m≥ k\) vertices with end-vertices in its \( (k-3)/2\)-disintegration, then \(G\) contains either a cycle of length at least \(k\) or a specific family of graphs. As an application, we strengthen the Erdős–Gallai stablity theorem of Füredi, Kostochka, Luo, and Verstraëte.
No takes yet. Share an insight, caveat, or question.
Ma et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: