Graphs with Diameter $n-e$ Minimizing the Spectral Radius

Abstract

The spectral radius $\rho (G)$ of a graph $G$ is the largest eigenvalue of its adjacency matrix $A(G)$. For a fixed integer $e\ge 1$, let $G_{n,n-e}^{min}$ be a graph with minimal spectral radius among all connected graphs on $n$ vertices with diameter $n-e$. Let $P_{n_1,n_2,...,n_t,p}^{m_1,m_2,...,m_t}$ be a tree obtained from a path of $p$ vertices ($0\sim 1\sim 2\sim ...\sim (p-1)$) by linking one pendant path $P_{n_i}$ at $m_i$ for each $i\in \{1,2,...,t\}$. For $e=1,2,3,4,5$, $G_{n,n-e}^{min}$ were determined in the literature. Cioabǎ-van Dam-Koolen-Lee \cite{CDK} conjectured for fixed $e\ge 6$, $G_{n,n-e}^{min}$ is in the family ${\mathcal{P}}_{n,e}=\{P_{2,1,...1,2,n-e+1}^{2,m_2,...,m_{e-4},n-e-2}\mid 2<m_2<...<m_{e-4}<n-e-2\}$. For $e=6,7$, they conjectured $G_{n,n-6}^{min}=P_{2,1,2,n-5}^{2,\lceil \frac{D-1}{2}\rceil ,D-2}$ and $G_{n,n-7}^{min}=P_{2,1,1,2,n-6}^{2,\lfloor \frac{D+2}{3}\rfloor ,D-\lfloor \frac{D+2}{3}\rfloor ,D-2}$. In this paper, we settle their three conjectures positively. We also determine $G_{n,n-8}^{min}$ in this paper.