A spectral version of Mantel's theorem

被引:31
作者
Zhai, Mingqing [1 ]
Shu, Jinlong [2 ]
机构
[1] Chuzhou Univ, Sch Math & Finance, Chuzhou 239012, Anhui, Peoples R China
[2] East China Normal Univ, Sch Data Sci & Engn, Shanghai 200237, Peoples R China
基金
中国国家自然科学基金;
关键词
Mantel's theorem; Spectral radius; Triangle; Quadrilateral; RADIUS; BOUNDS;
D O I
10.1016/j.disc.2021.112630
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数:10
相关论文
共 19 条
[1]   Cliques and the spectral radius [J].
Bollobas, Bela ;
Nikiforov, Vladimir .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (05) :859-865
[2]  
COLLATZ L, 1957, ABH MATH SEM HAMBURG, V21, P63, DOI DOI 10.1007/BF02941924
[3]  
Cvetkovic D., 2010, An Introduction to the Theory of Graph Spectra, DOI DOI 10.1017/CBO9780511801518
[4]   LOWER BOUNDS FOR THE CLIQUE AND THE CHROMATIC-NUMBERS OF A GRAPH [J].
EDWARDS, CS ;
ELPHICK, CH .
DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) :51-64
[5]  
Erdos P., 1966, STUD SCI MATH HUNG, V1, P215
[6]  
Füredi Z, 2013, BOLYAI SOC MATH STUD, V25, P169
[7]   GRAPHS WITHOUT QUADRILATERALS [J].
FUREDI, Z .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 34 (02) :187-190
[8]   On the number of edges of quadrilateral-free graphs [J].
Furedi, Z .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 68 (01) :1-6
[9]  
Hoffman AJ., 1975, RECENT ADV GRAPH THE, P273
[10]  
KOVARI T, 1954, C MATH, V3, P50