The stability method, eigenvalues and cycles of consecutive lengths

Abstract

Woodall proved that for a graph $G$ of order $n\ge 2k+3$ where $k\ge 0$ is an integer, if $e(G)\ge \left(\genfrac{}{}{0ex}{}{n-k-1}{2}\right)+\left(\genfrac{}{}{0ex}{}{k+2}{2}\right)+1$ then $G$ contains a $C_{\ell }$ for each $\ell \in [3,n-k]$. In this article, we prove a stability result of this theorem. As a byproduct, we give complete solutions to two problems in \cite{GN19}. Our second part is devoted to an open problem by Nikiforov: what is the maximum $C$ such that for all positive $\epsilon <C$ and sufficiently large $n$, every graph $G$ of order $n$ with spectral radius $\ddot{I}(G)>\sqrt{\lfloor \frac{n^2}{4}\rfloor }$ contains a cycle of length $\ell$ for every $\ell \le (C-\epsilon )n$. We prove that $C\ge \frac{1}{4}$ by a method different from previous ones, improving the existing bounds. We also derive an Erdős-Gallai type edge number condition for even cycles, which may be of independent interest.

13 pages