An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian

Abstract

The authors give a new upper bound for the diameter $D( G )$ of a graph G in terms of the eigenvalues of the Laplacian of G. The bound is \[ D ( G ) \leq \left\lfloor \frac{\text{cosh}^{ - 1} ( n - 1 )}{\text{cosh}^{ - 1} ( \frac{\lambda _n + \lambda _2 }{\lambda _n - \lambda _2 } )} \right\rfloor + 1, \] where $0 \leq \lambda _2 \leq \cdots \leq \lambda _n $ are the eigenvalues of the Laplacian of G and where $\lfloor {} \rfloor $ is the floor function.