2019/10/28 by Lin, Huiqiu, Ning, Bo, Wu, Baoyindureng · 14 citations
#05C50 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1910.12474
Bollobá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 λ21(G)+λ22(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 G of order n and size m contains a triangle, if one of the following is true: (1) λ1(G)≥√(m-1) and G≠ C5∪ (n-5)K1; and (2) λ1(G)≥ λ1(S(K\lfloor(n-1)/(2)\rfloor,\lceil(n-1)/(2)\rceil)) and G≠ S(K\lfloor(n-1)/(2)\rfloor,\lceil(n-1)/(2)\rceil), where S(K\lfloor(n-1)/(2)\rfloor,\lceil(n-1)/(2)\rceil) is obtained from K\lfloor(n-1)/(2)\rfloor,\lceil(n-1)/(2)\rceil by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.