Name
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. |
Year | Venue | Field |
|---|---|---|
2012 | CoRR | Discrete mathematics,Binary logarithm,Laplacian matrix,Combinatorics,Upper and lower bounds,Distance,Connectivity,Eigenvalues and eigenvectors,Mathematics,Lambda,Laplace operator |
DocType | Volume | Citations |
Journal | abs/1212.2701 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shayan Oveis Gharan | 1 | 323 | 26.63 |
| Luca Trevisan | 2 | 2995 | 232.34 |