Eigenvalues and triangles in graphs

Abstract

Bollobás and Nikiforov [J. Combin. Theory, Ser. B. 97 (2007) 859--865] conjectured the following. If $G$ is a $K_{r+1}$-free graph on at least $r+1$ vertices and $m$ edges, then $\hat{I}{»}_1^2(G)+\hat{I}{»}_2^2(G)\le \frac{r-1}{r}\cdot 2m$, where $\hat{I}{»}_1(G)$ and $\hat{I}{»}_2(G)$ are the largest and the second largest eigenvalues of the adjacency matrix $A(G)$, respectively. In this paper, we confirm the conjecture in the case $r=2$, by using tools from doubly stochastic matrix theory, and also characterize all families of extremal graphs. Motivated by classic theorems due to Erdős and Nosal respectively, we prove that every non-bipartite graph $G$ of order $n$ and size $m$ contains a triangle, if one of the following is true: (1) $\hat{I}{»}_1(G)\ge \sqrt{m-1}$ and $G\ne C_5\cup (n-5)K_1$; and (2) $\hat{I}{»}_1(G)\ge \hat{I}{»}_1(S(K_{\lfloor \frac{n-1}{2}\rfloor ,\lceil \frac{n-1}{2}\rceil }))$ and $G\ne S(K_{\lfloor \frac{n-1}{2}\rfloor ,\lceil \frac{n-1}{2}\rceil })$, where $S(K_{\lfloor \frac{n-1}{2}\rfloor ,\lceil \frac{n-1}{2}\rceil })$ is obtained from $K_{\lfloor \frac{n-1}{2}\rfloor ,\lceil \frac{n-1}{2}\rceil }$ by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.

15 pages, accepted version for publication in Combinatorics, Probability and Computing