Document Zbl 1508.05107 - zbMATH Open

Spectral radius conditions for the existence of all subtrees of diameter at most four. (English) Zbl 1508.05107

Summary: Let \(\mu(G)\) denote the spectral radius of a graph \(G\). We partly confirm a conjecture due to V. Nikiforov [ibid. 432, No. 9, 2243–2256 (2010; Zbl 1217.05152)], 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}\) be the graph obtained by joining every vertex of a complete graph on \(k\) vertices to every vertex of an independent set of order \(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 [loc. cit.] that for a given integer \(k\), every graph \(G\) of sufficiently large order \(n\) with \(\mu(G) \geq \mu( S_{n, k}^+)\) contains all trees of order \(2 k + 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 \geq 8\). If a graph \(G\) with sufficiently large order \(n\) satisfies \(\mu(G) \geq \mu( S_{n, k})\) and \(G \neq S_{n, k}\), then \(G\) contains all trees of order \(2 k + 3\) with diameter at most four, except for the tree obtained from a star on \(k + 2\) vertices by subdividing each of its \(k + 1\) edges once.