The stability method, eigenvalues and cycles of consecutive lengths


الملخص بالإنكليزية

Woodall proved that for a graph $G$ of order $ngeq 2k+3$ where $kgeq 0$ is an integer, if $e(G)geq binom{n-k-1}{2}+binom{k+2}{2}+1$ then $G$ contains a $C_{ell}$ for each $ellin [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 $varepsilon<C$ and sufficiently large $n$, every graph $G$ of order $n$ with spectral radius $rho(G)>sqrt{lfloorfrac{n^2}{4}rfloor}$ contains a cycle of length $ell$ for every $ellleq (C-varepsilon)n$. We prove that $Cgeqfrac{1}{4}$ by a method different from previous ones, improving the existing bounds. We also derive an ErdH{o}s-Gallai type edge number condition for even cycles, which may be of independent interest.

تحميل البحث