Eigenvalues and triangles in graphs

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 λ ₁²(G) + λ ₂²(G) ≤ (r - 1)/r · 2m , where λ 1 ( G )and λ 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 of order and size contains a triangle if one of the following is true: (i) λ ₁(G) ≥ √m - 1 and G ≠ C₅ ∪ (n - 5)K₁ , and (ii) λ ₁(G) ≥ λ ₁(S(K[(n - 1)/2],[(n - 1)/2])) and G ≠ S(K[(n - 1)/2],[(n - 1)/2]) , where S(K[(n - 1)/2],[(n - 1)/2]) is obtained from K[(n - 1)/2],[(n - 1)/2] by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.