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 ${\lambda }_1^2(G)+{\lambda }_2^2(G)\le \frac{r-1}{r}\cdot 2m$, where ${\lambda }_1(G)$ and ${\lambda }_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) ${\lambda }_1(G)\ge \sqrt{m-1}$ and $G\ne C_5\cup (n-5)K_1$; and (2) ${\lambda }_1(G)\ge {\lambda }_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

Cited by in corpus (11)

• Spectral extremal graphs for the bowtie
• Signless Laplacian spectral radius of graphs without short cycles or long cycles
• Refinement on spectral Turán's theorem
• Counting substructures and eigenvalues I: triangles
• Spectral extrema of graphs with fixed size: forbidden a fan graph, friendship graph or theta graph
• Spectral supersaturation: Triangles and bowties
• A spectral Erdős-Faudree-Rousseau theorem
• A spectral Erdős-Rademacher theorem
• Spectral Turán problem of non-bipartite graphs: Forbidden books
• Variants of spectral Turán theorems and eigenvectors of graphs
• Spectral extremal problems for non-bipartite graphs without odd cycles