Stability of Woodall's theorem and spectral conditions for large cycles (Q2692178): Difference between revisions

Summary: \textit{P. Erdős} [in: Combinat. Math. Appl., Proc. Conf. Math. Inst., Oxford 1969, 97--109 (1971; Zbl 0221.05051)] asked how many edges are needed in a graph on \(n\) vertices, to ensure the existence of a cycle of length exactly \(n-k\). In this paper, we consider the spectral analog of Erdős' problem. Indeed, the problem of determining tight spectral radius conditions for cycles of length \(\ell\) in a graph of order \(n\) for each \(\ell \in[3,n]\) seems very difficult. We determine tight spectral radius conditions for \(C_{\ell}\) where \(\ell\) belongs to an interval of the form \([n-\Theta(\sqrt{n}),n]\). As a main tool, we prove a stability result of a theorem due to \textit{D. R. Woodall} [Proc. Lond. Math. Soc. (3) 24, 739--755 (1972; Zbl 0233.05117)], which states that for a graph \(G\) of order \(n\geqslant 2k+3\) where \(k\geqslant 0\) is an integer, if \(e(G)>\binom{n-k-1}{2}+\binom{k+2}{2}\) then \(G\) contains a \(C_{\ell}\) for each \(\ell\in [3,n-k]\). We prove a tight spectral condition for the circumference of a \(2\)-connected graph with a given minimum degree, of which the main tool is a stability version of a conjecture of \textit{D. R. Woodall} [Acta Math. Acad. Sci. Hung. 28, 77--80 (1976; Zbl 0337.05128)] on circumference of a \(2\)-connected graph with a given minimum degree proved by \textit{J. Ma} and \textit{B. Ning} [Combinatorica 40, No. 1, 105--147 (2020; Zbl 1449.05163)]. We also give a brief survey on this area and point out where we are and our predicament.