Bollobás-Nikiforov conjecture holds asymptotically almost surely

Abstract

Bollobás and Nikiforov (J. Combin. Theory Ser. B. 97 (2007) 859-865) conjectured that for a graph $G$ with $e(G)$ edges and the clique number $\omega (G)$, then ${\lambda }_1^2+{\lambda }_2^2\le 2e(G)\left(1-\frac{1}{\omega (G)}\right),$ where ${\lambda }_1$ and ${\lambda }_2$ are the largest and the second largest eigenvalues of the adjacency matrix of $G$, respectively. In this paper, we prove that for a sequence of random graphs the conjecture holds true with probability tending to one as the number of vertices tends to infinity.