A Spectral Erdős-Sós Theorem
Sebastian M. Cioabă, Dheer Noal Desai, Michael Tait
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\gt 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.KeywordsErdős–Sós conjecturespectral extremalTurán-type problemBrualdi–Solheid problemspectral radiusMSC codes05C3505C5015A18