Unified approach to the generalized Turán problem and supersaturation

PASS

The reconstruction matches the paper’s surrounding context: it concerns extending Nikiforov’s inequality

from even $k$ to odd $k$. The star $K_{1,s}$ is a valid counterexample: the walk counts and spectral radius are correct, and for odd $k=2a+1$, $r=1$,

for $s>1$. Thus the odd-$k$ extension is rigorously disproved. I found no prior literature source explicitly giving this counterexample or a stronger resolution.

Novelty assessment

KNOWN

Classification rationale: The accepted resolution is not new as a resolution of Nikiforov’s walk-counting problem. A 2020 paper explicitly titled “Walk counting and Nikiforov’s problem” gives a negative answer by constructing infinite families of connected bipartite counterexamples. The star example may be a simple self-contained counterexample to a variant/indexing of the inequality, but the falsehood of the proposed extension was already known.

Literature check: I checked the original Nikiforov paper/arXiv record and searched citing/related works for “walks,” “spectral radius,” “Nikiforov problem,” and the ratio $w_{s+r}/w_s$. The decisive reference is Feng–Lu–Stevanović (2020), whose abstract states that Nikiforov asked whether the relevant walk-count inequality holds and that the authors “provide a negative answer” via infinite connected bipartite graph families. Their notation counts walks by number of vertices, so it differs by an index shift from the solution’s length convention, but it is the same/sufficiently stronger negative resolution.

Citation: Lihua Feng, Lu Lu, Dragan Stevanović, “Walk counting and Nikiforov’s problem,” Open Journal of Discrete Applied Mathematics 3(1) (2020), 11–19. DOI: 10.30538/psrp-odam2020.0024.