A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues

Shayan Oveis Gharan, Luca Trevisan

We prove that the diameter of any unweighted connected graph G is O(k log n/lambda_k), for any k>= 2. Here, lambda_k is the k smallest eigenvalue of the normalized laplacian of G.…