文献类型：期刊文献

英文题名：Eigenvalues and triangles in graphs

作者：Lin, Huiqiu[1];Ning, Bo[2];Wu, Baoyindureng[3]

机构：[1]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China;[2]Nankai Univ, Coll Comp Sci, Tianjin 300071, Peoples R China;[3]Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China

年份：2021

卷号：30

期号：2

起止页码：258

外文期刊名：COMBINATORICS PROBABILITY AND COMPUTING

收录：;EI(收录号：20204209340320);WOS:【SCI-EXPANDED(收录号:WOS:000625213500006)】；

基金：Research supported by NSFC (grants 11771141 and 12011530064).This work is supported by NSFC (No. 11971346).Research supported by NSFC (grant 11571294).

语种：英文

外文关键词：Eigenvalues and eigenfunctions - Graph theory

摘要：Bollobas and Nikiforov (J. Combin. Theory Ser. B. 97 (2007) 859-865) conjectured the following. If G is a Kr+1-free graph on at least r + 1 vertices and m edges, then lambda(2)(1)(G) + lambda(2)(2) (G) <= (r - 1)/r center dot 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 Erdos 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) lambda(1)(G) >= root m - 1 and G not equal C-5 boolean OR (n- 5)K-1, and (ii) lambda(1)(G) >= lambda(.)1(S(K-[(n-1)/2],K-[(n-1)/2])) and G not equal S(K-[(n-1)/2],K-[(n-1)/2]), where S(K-[(n-1)/2],K-[(n-1)/2]) is obtained from K-[(n-1)/2],K-[(n-1)/2] by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.