A spectral Erdős-Sós theorem

Abstract

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\ge 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.