Diameter vs. Laplacian eigenvalue distribution

Abstract

Let $G$ be a simple graph of order $n$. It is known that any Laplacian eigenvalue of $G$ belongs to the interval $[0,n]$. For an interval $I\subseteq [0, n]$, denote by $m_GI$ the number of Laplacian eigenvalues of $G$ in $I$, counted with multiplicities. Let $d$ be the diameter of $G$. If $2\le d\le n-4$, we show that $m_G[n-d,n]\le n-d+2$, and it may be improved into $m_G[n-d,n]\le n-d+1$ when $d=2,3,4$. We also show that $m_G[n-2d+4,n]\le n-2$ if $d=2, \lfloor\frac{n+3}{2}\rfloor$, and $m_G[n-2d+4,n]\le n-3$ if $3\le d\le \lfloor\frac{n+1}{2}\rfloor$. The diameter constraint provides an insightful approach to understand how the Laplacian eigenvalues are distributed.