Graph curvature via resistance distance
Preprint
Abstract
Let $G=(V,E)$ be a finite, combinatorial graph. We define a notion of curvature on the vertices $V$ via the inverse of the resistance distance matrix. We prove that this notion of curvature has a number of desirable properties. Graphs with curvature bounded from below by $K>0$ have diameter bounded from above. The Laplacian $L=D-A$ satisfies a Lichnerowicz estimate, there is a spectral gap $\lambda_2 \geq 2K$. We obtain matching two-sided bounds on the maximal commute time between any two vertices in terms of $|E| \cdot |V|^{-1} \cdot K^{-1}$. Moreover, we derive quantitative rates for the mixing time of the corresponding Markov chain and prove a general equilibrium result.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Curvature on graphs via equilibrium measuresJournal of Graph Theory, 2023
- Minimizing Kirchhoff index among graphs with a given vertex bipartitenessApplied Mathematics and Computation, 2016
- On resistance-distance and Kirchhoff indexJournal of Mathematical Chemistry, 2008
- Resistance distance and Kirchhoff index in circulant graphsInternational Journal of Quantum Chemistry, 2006
- On the geometry of metric measure spaces. IIActa Mathematica, 2006
- Resistance distance and Laplacian spectrumTheoretical Chemistry Accounts, 2003
- Bochner's Method for Cell Complexes and Combinatorial Ricci CurvatureDiscrete & Computational Geometry, 2003
- Combinatorial curvature for planar graphsJournal of Graph Theory, 2001
- Asymptotic analysis of a random walk on a hypercube with many dimensionsRandom Structures & Algorithms, 1990
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985