The spectral radius of graphs without trees of diameter at most 4

Xinmin Hou, Boyuan Liu, Yu Qiu, Lei Yu

Published 2016-10-04Version 1

Nikiforov conjectured that for given integer $k$, any graph $G$ of sufficiently large order $n$ with spectral radius $\mu(G)\geq \mu(S_{n,k})$ (or $\mu(G)\ge \mu(S_{n,k}^+))$ contains all trees of order $2k+2$ (or $2k+3)$, unless $G=S_{n,k}$ (or $G=S_{n,k}^+)$, where $S_{n,k}=K_k\vee \overline{K_{n-k}}$, the join of a complete graph on $k$ and an empty graph on $n-k$ vertices, and $S_{n,k}^+$ is the graph obtained from $S_{n,k}$ by adding an edge in the independent set of $S_{n,k}$. In this paper, we prove that $S_{n,k}$ is the unique extremal graph with maximum spectral radius among all of the graphs of order $n$ containing no trees of order $2k+3$ and diameter at most 4 but an exception.