The Bollobás--Nikiforov Conjecture for Complete Multipartite Graphs and Dense $K_4$-Free Graphs

Abstract

The Bollobás--Nikiforov conjecture asserts that for any graph $G\ne K_n$ with $m$ edges and clique number $\omega (G)$, \[ λ_1^2(G) + λ_2^2(G) \;\leq\; 2\!\left(1 - \frac{1}{ω(G)}\right)m, \] where ${\lambda }_1(G)\ge {\lambda }_2(G)\ge \cdots \ge {\lambda }_n(G)$ are the adjacency eigenvalues of $G$. We prove the conjecture for all complete multipartite graphs $K_{n_1,\dots ,n_r}$ with $n_1+\cdots +n_r>r$. The proof computes the full spectrum via a secular equation, establishes that ${\lambda }_2=0$ whenever the graph has more vertices than parts, and then applies Nikiforov's spectral Turán theorem; equality holds if and only if all parts have equal size. We also prove a stability result for $K_4$-free graphs whose spectral radius is near the Turán maximum: such graphs are structurally close to the balanced complete tripartite graph, and as a consequence the conjecture holds for all $K_4$-free graphs with $m=\Omega (n^2)$ when $n$ is sufficiently large. Finally, we identify the precise obstruction preventing a Hoffman-bound approach from settling the conjecture for $K_4$-free graphs with independence number $\alpha (G)\ge n/3$.

13 pages version 2