数学
二部图
完全二部图
边传递图
光谱半径
组合数学
图形
离散数学
四边形的
电压图
折线图
特征向量
量子力学
热力学
物理
有限元法
作者
Mingqing Zhai,Jinlong Shu
标识
DOI:10.1016/j.disc.2021.112630
摘要
A classic result in extremal graph theory, known as Mantel's theorem, implies that every non-bipartite graph of order n with size m>⌊n2/4⌋ contains a triangle. Recently, by majority technique, Lin, Ning and Wu obtained a spectral version as follows: every non-bipartite graph G of size m with spectral radius ρ(G)≥m−1 contains a triangle unless G≅C5. In this paper, by using completely different techniques we show that every non-bipartite graph G of size m with ρ(G)≥ρ⁎(m) contains a triangle unless G≅SK2,m−12, where ρ⁎(m) is the largest root of x3−x2−(m−2)x+(m−3)=0 and SK2,m−12 is obtained by subdividing an edge of K2,m−12. 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 ρ(G)≥ρ(K1,m−1+e) contains a quadrilateral unless G≅K1,m−1+e.
科研通智能强力驱动
Strongly Powered by AbleSci AI