Title: A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
Abstract: 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.
Publication Year: 2012
Publication Date: 2012-12-12
Language: en
Type: preprint
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot