Diameters of Graphs with Spectral Radius at most $3/2\sqrt{2}$

Abstract

The spectral radius $\rho (G)$ of a graph $G$ is the largest eigenvalue of its adjacency matrix. Woo and Neumaier discovered that a connected graph $G$ with $\rho (G)\le 3/2\sqrt{2}$ is either a dagger, an open quipu, or a closed quipu. The reverse statement is not true. Many open quipus and closed quipus have spectral radius greater than $3/2\sqrt{2}$. In this paper we proved the following results. For any open quipu $G$ on $n$ vertices ($n\ge 6$) with spectral radius less than $3/2\sqrt{2}$, its diameter $D(G)$ satisfies $D(G)\ge (2n-4)/3$. This bound is tight. For any closed quipu $G$ on $n$ vertices ($n\ge 13$) with spectral radius less than $3/2\sqrt{2}$, its diameter $D(G)$ satisfies $\frac{n}{3}<D(G)\le \frac{2n-2}{3}$. The upper bound is tight while the lower bound is asymptotically tight. Let $G_{n,D}^{min}$ be a graph with minimal spectral radius among all connected graphs on $n$ vertices with diameter $D$. We applied the results and found $G_{n,D}^{min}$ for some range of $D$. For $n\ge 13$ and $D\in [\frac{n}{2},\frac{2n-7}{3}]$, we proved that $G_{n,D}^{min}$ is the graph obtained by attaching two paths of length $D-\lfloor \frac{n}{2}\rfloor$ and $D-\lceil \frac{n}{2}\rceil$ to a pair of antipodal vertices of the even cycle $C_{2(n-D)}$. Thus we settled a conjecture of Cioab-van Dam-Koolen-Lee, who previously proved a special case $D=\frac{n+e}{2}$ for $e=1,2,3,4$.

arXiv comment18 pages