A Robust Bollobás-Nikiforov Bound for Graphs Close to Triangle-Free Graphs

Abstract

The Bollobás-Nikiforov (BN) conjecture, in its clique-number form, asserts that every non-complete graph $G$ of order $n$ with $m$ edges and clique number $\omega(G)$ satisfies
\[
\lambda_1(G)^2+\lambda_2(G)^2
\le 2\left(1-\frac1{\omega(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 an unconditional perturbative form for graphs that can be made triangle-free by deleting few edges. Let $\eta_{\triangle}(G)$ be the minimum number of edges whose deletion destroys all triangles of $G$. Every non-complete graph $G$ on at least two vertices satisfies
\[
\lambda_1(G)^2+\lambda_2(G)^2
\le 2\left(1-\frac1\omega\right)m+C_\omega \eta_{\triangle}(G),
\]
where $\omega=\omega(G)$ and
\[
C_\omega=2+\frac2\omega+\frac{4\omega}{\omega-2}
\qquad (\omega\ge3).
\]
For $\omega=1,2$, no additive error is needed. Since $C_\omega\le 44/3$, a uniform error term $(44/3) \eta_{\triangle}(G)$ is valid. The emphasis of the result is the explicit finite error that is linear in the edge-deletion distance from the triangle-free class. We also show that the vertex-disjoint triangle packing number cannot replace $\eta_{\triangle}(G)$ in this perturbative framework, and we clarify the relation with bounds expressed in terms of the total number of triangles.