Back to Search
Start Over
Spectral radius conditions for the existence of all subtrees of diameter at most four
- Source :
- Linear Algebra and its Applications, 663 (2023), 80-101
- Publication Year :
- 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 Erd\H{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}\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)\geq \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\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 $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.<br />Comment: 16 pages
- Subjects :
- Mathematics - Combinatorics
05C50, 05C35
Subjects
Details
- Database :
- arXiv
- Journal :
- Linear Algebra and its Applications, 663 (2023), 80-101
- Publication Type :
- Report
- Accession number :
- edsarx.2109.11546
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.laa.2023.01.004