%0 Journal Article
%T A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
%A Shayan Oveis Gharan
%A Luca Trevisan
%J Computer Science
%D 2012
%I arXiv
%X 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. This solves a problem posed by Gil Kalai.
%U http://arxiv.org/abs/1212.2701v1