论文标题
在Turán定理的光谱上进行改进
Refinement on spectral Turán's theorem
论文作者
论文摘要
由于Nosal和Nikiforov，极端光谱图理论的一个众所周知的结果指出，如果$ g $是$ n $顶点上的无三角形图，则$λ（g）\leλ（k _ {\ lfloor \ lfloor \ lfloar \ frac \ frac {n} }）$，仅在且仅当$ g = k = k _ {\ lfloor \ frac {n} {2} {2} \ rfloor，\ lceil \ frac {n} {2} {2} \ rceil} $时。 Nikiforov [线性代数应用。 427（2007）]将此结果扩展到$ k_ {r+1} $ - 每个整数$ r \ ge 2 $的免费图。这就是Turán定理的光谱。最近，Lin，Ning和Wu [Combin。概率。计算。 30（2021）]证明了非双方三角形图对此结果进行了改进。在本文中，我们为Nikiforov和Lin，Ning和Wu的结果提供了替代证明。我们的证明可以使我们可以将以后的结果扩展到非$ r $ -partite $ k_ {r+1} $ - 免费图形。我们的结果完善了Nikiforov的定理，也可以将其视为Brouwer定理的光谱版本。
A well-known result in extremal spectral graph theory, due to Nosal and Nikiforov, states that if $G$ is a triangle-free graph on $n$ vertices, then $λ(G) \le λ(K_{\lfloor \frac{n}{2}\rfloor, \lceil \frac{n}{2} \rceil })$, equality holds if and only if $G=K_{\lfloor \frac{n}{2}\rfloor, \lceil \frac{n}{2} \rceil }$. Nikiforov [Linear Algebra Appl. 427 (2007)] extended this result to $K_{r+1}$-free graphs for every integer $r\ge 2$. This is known as the spectral Turán theorem. Recently, Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)] proved a refinement on this result for non-bipartite triangle-free graphs. In this paper, we provide alternative proofs for the result of Nikiforov and the result of Lin, Ning and Wu. Our proof can allow us to extend the later result to non-$r$-partite $K_{r+1}$-free graphs. Our result refines the theorem of Nikiforov and it also can be viewed as a spectral version of a theorem of Brouwer.
