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

DOI10.1016/J.LAA.2023.01.004zbMATH Open1508.05107arXiv2109.11546MaRDI QIDQ6378422

Xiangxiang Liu, Hajo J. Broersma, Li-Gong Wang

Publication date: 23 September 2021

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 ErdH{o}s-S'os 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}veeoverline{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)geqmu(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 $kgeq8$. If a graph $G$ with sufficiently large order $n$ satisfies $mu(G)geqmu(S_{n,k})$ and $Geq{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.

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12)

This page was built for publication: Spectral radius conditions for the existence of all subtrees of diameter at most four