UVictoria Discrete Math Seminar: Shivaramakrishna Pragada

Let $G$ be a graph with $n$ vertices. Let $A(G)$ be its adjacency matrix. Let $\lambda_1(G), \lambda_2(G)$ denote the largest and second largest eigenvalues of the adjacency matrix. Bollob\'{a}s and Nikiforov (2007) conjectured that for any graph $G \neq K_n$ with $m$ edges \[\lambda_1^2+\lambda_2^2\le \bigg( 1-\frac{1}{\omega(G)}\bigg)2m,\] where $\omega(G)$ denotes the clique number of $G$. In this talk, we prove this conjecture for graphs with not so many triangles, using the method of triangle counting. This is a joint work with Hitesh Kumar.