Nikiforov's spectral consecutive cycle problem and the connected-matching method

Abstract

Let $ρ(G)$ denote the adjacency spectral radius of a graph $G$ of order $n$. We determine the sharp constant in an open problem of Nikiforov (2008) on cycles of consecutive lengths. For every $\varepsilon>0$ and all sufficiently large $n$, if $G$ is an $n$-vertex graph with $ρ(G)>\sqrt{\lfloor{n^2/4}\rfloor},$ then $G$ contains a cycle $C_\ell$ for every integer length $3\le \ell\le (\frac{3-\sqrt5}{2}-\varepsilon)n.$ The constant $(3-\sqrt5)/2$ is best possible, as shown by the split graph $K_k\vee\overline K_{n-k}$ with $k\sim(3-\sqrt5)n/4$. Our result improves all previous results [LAA2008, CPC2020, JGT2023, JGT2023, GC2024]. The proof combines the degree form of Szemerédi's regularity lemma, a spectral matching theorem of Feng-Yu-Zhang, Weyl's inequality, a refinement of Łuczak's connected-matching embedding method, and other ideas.

Disclosure

“for sharing his ideas on constructing consecutive odd cycles in an email, before the arXiv version of [2] was submitted. This directly led to the joint work [10] and indirectly to the reading of [13]. Declaration of AI usage The AI (Chatgpt 5.6) assistant helped with proofreading, grammar checking, and language polishing. In particular, the second author and AI independently found gaps for the original proof of Lemma 3.4. The current version of Lemma 3.4 and its proof were or”

PDF page 19

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:08:40.175500Z

Structural counts