Eigenvalues and triangles in graphs

Huiqiu Lin, Bo Ning, Baoyindureng Wu

Published 2019-10-28Version 1

Bollob\'as and Nikiforov (J. Combin. Theory, Ser. B. 97 (2007) 859--865) conjectured the following. If $G$ is a $K_{r+1}$-free graph of order at least $r+1$ with $m$ edges, then $\la^2_1(G)+\la^2_2(G)\leq \frac{r-1}{r}2m$, where $\la_1(G)$ and $\la_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 classical theorems due to Erd\H{o}s and Nosal, 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) $\la_1(G)\geq\sqrt{m-1}$ and $G\neq C_5$; and (2) $\la_1(G)\geq \la_1(S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil}))$ and $G\neq 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.