文献类型：期刊文献

英文题名：Eigenvalues and triangles in graphs

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

机构：[1] Department of Mathematics, East China University of Science and Technology, Shanhai, 200237, China; [2] School of Mathematics, Tianjin University, Tianjin, 300072, China; [3] College of Mathematics and System Science, Xinjiang University, Xinjiang, Urumqi, 830046, China

年份：2020

外文期刊名：arXiv

收录：EI(收录号：20200296373)

语种：英文

外文关键词：C (programming language) - Matrix algebra - Stochastic systems - Undirected graphs

摘要：MSC Codes 05C50Bollobás 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 (Formula presented), 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 Erdo?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) λ1(G) ≥ √m ? 1 and G 6≠ C5 ∪ (n ? 5)K1; and (Formula presented) and (Formula presented), where (Formula presented) is obtained from (Formula presented) by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems. Copyright ? 2020, The Authors. All rights reserved.