Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1017/S0963548320000462 | COMBINATORICS PROBABILITY & COMPUTING |
DocType | Volume | Issue |
Journal | 30 | 2 |
ISSN | Citations | PageRank |
0963-5483 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Huiqiu Lin | 1 | 34 | 11.56 |
| Bo Ning | 2 | 18 | 8.86 |
| Baoyindureng Wu | 3 | 99 | 24.68 |