Spectral radius conditions for the existence of all subtrees of diameter at most four

Abstract

Let $\mu (G)$ denote the spectral radius of a graph $G$. We partly confirm a conjecture due to Nikiforov, which is a spectral radius analogue of the well-known Erdős-Sós Conjecture that any tree of order $t$ is contained in a graph of average degree greater than $t-2$. Let $S_{n,k}=K_k\vee \overline{K_{n-k}}$, and let $S_{n,k}^{+}$ be the graph obtained from $S_{n,k}$ by adding a single edge joining two vertices of the independent set of $S_{n,k}$. In 2010, Nikiforov conjectured that for a given integer $k$, every graph $G$ of sufficiently large order $n$ with $\mu (G)\ge \mu (S_{n,k}^{+})$ contains all trees of order $2k+3$, unless $G=S_{n,k}^{+}$. We confirm this conjecture for trees with diameter at most four, with one exception. In fact, we prove the following stronger result for $k\ge 8$. If a graph $G$ with sufficiently large order $n$ satisfies $\mu (G)\ge \mu (S_{n,k})$ and $G\ne S_{n,k}$, then $G$ contains all trees of order $2k+3$ with diameter at most four, except for the tree obtained from a star $K_{1,k+1}$ by subdividing each of its $k+1$ edges once.

arXiv comment16 pages