Current browse context:
math.CO
Change to browse by:
References & Citations
Mathematics > Combinatorics
Title: Curvature, diameter and signs of graphs
(Submitted on 24 Apr 2024)
Abstract: We prove a Li-Yau type eigenvalue-diameter estimate for signed graphs. That is, the nonzero eigenvalues of the Laplacian of a non-negatively curved signed graph are lower bounded by $1/D^2$ up to a constant, where $D$ stands for the diameter. This leads to several interesting applications, including a volume estimate for non-negatively curved signed graphs in terms of frustration index and diameter, and a two-sided Li-Yau estimate for triangle-free graphs. Our proof is built upon a combination of Chung-Lin-Yau type gradient estimate and a new trick involving strong nodal domain walks of signed graphs. We further discuss extensions of part of our results to nonlinear Laplacians on signed graphs.
Link back to: arXiv, form interface, contact.