论文标题
光谱erdős-sós定理
A spectral Erdős-Sós theorem
论文作者
论文摘要
著名的Erdős-Sós的猜想指出，平均程度的每个图都超过$ t-1 $必须包含$ t+1 $顶点上的每棵树。在本文中，我们研究了该猜想的光谱版本。对于$ n> k $，令$ s_ {n，k} $为$ k $ vertices上的一个集团的联接，带有独立的$ n-k $ vertices，并用$ s_ {n，k}^+$表示从$ s_ {n，k}获得的图表，通过添加一个边缘。我们表明，对于固定的$ k \ geq 2 $和足够大的$ n $，如果$ n $ vertices上的图形至少具有邻接光谱半径，至少高达$ s_ {n，k} $，并且不是同构至$ s_ {n，k} $，则它将其包含在$ 2K+2 $ Vertices上的所有树。同样，如果足够大的图具有光谱半径至少与$ s_ {n，k}^+$一样大，则它要么包含$ 2K+3 $ vertices上的所有树，要么是同构，或对$ s_ {n，k}^+$。这回答了Nikiforov的两部分猜想。
The famous Erdős-Sós conjecture states that every graph of average degree more than $t-1$ must contain every tree on $t+1$ vertices. In this paper, we study a spectral version of this conjecture. For $n>k$, let $S_{n,k}$ be the join of a clique on $k$ vertices with an independent set of $n-k$ vertices and denote by $S_{n,k}^+$ the graph obtained from $S_{n,k}$ by adding one edge. We show that for fixed $k\geq 2$ and sufficiently large $n$, if a graph on $n$ vertices has adjacency spectral radius at least as large as $S_{n,k}$ and is not isomorphic to $S_{n,k}$, then it contains all trees on $2k+2$ vertices. Similarly, if a sufficiently large graph has spectral radius at least as large as $S_{n,k}^+$, then it either contains all trees on $2k+3$ vertices or is isomorphic to $S_{n,k}^+$. This answers a two-part conjecture of Nikiforov affirmatively.
