Stability of Woodall's theorem and spectral conditions for large cycles

Binlong Li¹ ; Bo Ning

¹Northwestern Polytechnical University

The electronic journal of combinatorics, Tome 30 (2023) no. 1

Résumé

In the 1970s, Erdős 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 Woodall, which states that for a graph $G$ of order $n\geq 2k+3$ where $k\geq 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 1976 conjecture of Woodall on circumference of a $2$-connected graph with a given minimum degree proved by Ma and the second author. We also give a brief survey on this area and point out where we are and our predicament.

Détail

DOI : 10.37236/11641

Classification : 05C50, 05C35, 05C38, 05C12
Mots-clés : graph circumference, clique, closure operation, edge-switching technique, Hamiltonian graph, Woodall's conjecture, 2-connected graph