Eigenvalues and triangles in graphs. (28th March 2021)

• Record Type: Journal Article
• Authors: Lin, Huiqiu; Ning, Bo; Wu, Baoyindureng
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 2(2021)
• Page Start: 258
• Page End: 270
• Publication Date: 2021-03-28
• Subjects: 05C50; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000462
• Languages: English
• ISSNs: 0963-5483

Abstract

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 ${\rm{\lambda }}_1^2(G) + {\rm{\lambda }}_2^2(G) \le (r - 1)/r \cdot 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) ${{\rm{\lambda }}_1}(G) \ge \sqrt {m - 1} $ and $G \ne {C_5} \cup (n - 5){K_1}$, and (ii) ${{\rm{\lambda }}_1}(G) \ge {{\rm{\lambda }}_1}(S({K_{[(n - 1)/2], [(n - 1)/2]}}))$ and $G \ne 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.