A spectral version of Mantel's theorem

摘要

A classic result in extremal graph theory, known as Mantel's theorem, implies that every non-bipartite graph of order n with size m > left perpendicularn(2)/4right perpendicular contains a triangle. Recently, by bipartite graph G of size m with spectral radius rho(G) > >= root m -1 contains a triangle unless majority technique, Lin, Ning and Wu obtained a spectral version as follows: every non G congruent to C5. In this paper, by using completely different techniques we show that every non bipartite graph G of size m with rho(G) >= rho*(m) contains a triangle unless G congruent to SK2, m-1 2 , where rho*(m) is the largest root of x3 - x2 - (m - 2)x + (m -3) = 0 and SK2, m-1 2 is obtained by subdividing an edge of K-2, m-1/2 . This result implies both Mantel's theorem and Lin, Ning and Wu's result. Moreover, following Nikiforov's result, we also prove that every non bipartite graph G with m >= 26 and rho(G) > rho(K-1,K-m-1 + e) contains a quadrilateral unless G congruent to (K1,m-1) + e.

关键词