UVictoria Discrete Math Seminar: Shivaramakrishna Pragada
Topic
Triangle counting and Bollobas-Nikiforov conjecture
Speakers
Details
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.
Event Type
Scientific, Seminar
Date
November 7, 2024
Time
-
Location