Tight Bound for Nikiforov's Spectral Even-Cycle Conjecture

Nikiforov conjectured that, for every fixed $k\ge 2$ and all sufficiently large $n$, the unique $n$-vertex $C_{2k+2}$-free graph with maximum adjacency spectral radius is $S_{n,k}^{+}$, where $S_{n,k}=K_k\vee {\bar{K}}_{n-k}$ and $S_{n,k}^{+}$ is obtained from $S_{n,k}$ by adding one edge inside the independent part. Cioabă, Desai and Tait proved this conjecture for $n\ge k^{O(k)}$. Later, Li and Ning raised the problem of determining the optimal exponent $\gamma =\gamma (k)$ such that the same conclusion holds for $n\ge \mathrm{\Omega }(k^{\gamma (k)})$. We prove a stronger uniform theorem for Nikiforov’s matrices $A_{\alpha }(G)=\alpha D(G)+(1-\alpha )A(G)$. More precisely, for every $\epsilon >0$ there are constants $C_{\epsilon }$ and $k_{\epsilon }$ such that for all $0\le \alpha \le 1-\epsilon$, $k\ge k_{\epsilon }$ and $n\ge C_{\epsilon }k$, every $n$-vertex $C_{2k+2}$-free graph $G$ satisfies ${\rho }_{\alpha }(G)\le {\rho }_{\alpha }(S_{n,k}^{+})$, with equality if and only if $G\cong S_{n,k}^{+}$. In particular, the case $\alpha =0$ answers the problem of Li and Ning, and the $A_{\alpha }$-spectral even-cycle threshold is linear in $k$, uniformly for all $\alpha$ bounded away from $1$. Our proof introduces a weighted rooted Erdős–Gallai type path lemma, which may be of independent interest in Perron-vector methods for spectral extremal graph problems. The same method also yields asymptotically tight $A_{\alpha }$-spectral bounds for two local forbidden-subgraph families, namely $(K_1\vee P_{\mathrm{\ell }})$-free graphs and $F_s$-free graphs, where $F_s$ denotes the friendship graph.