A SPECTRAL ERDOS-SOS THEOREM

The famous Erdos-Sos 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,S- 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,S- k by adding one edge. We show that for fixed k >= 2 and sufficiently large n, if a graph on n vertices has adjacency spectral radius at least as large as S-n,S- k and is not isomorphic to Sn,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.