18 citations · 66 across the 15 of their papers we have counts for
Showing cs.DMShow all
2 papers · 1 filter
cs.DM2017
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
Nikhil Srivastava, Luca Trevisan
We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if is an -node weighted undirected graph of average combinatorial deg…
cs.DM2012★ 1 cited
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.…