Graphs with Nonnegative Resistance Curvature

Journal article

This article introduces and studies a new class of graphs motivated by discrete curvature. We call a graph resistance nonnegative if there exists a distribution on its spanning trees such that every vertex has expected degree at most two in a random spanning tree; these are precisely the graphs that admit a metric with nonnegative resistance curvature, a discrete curvature introduced by Devriendt and Lambiotte. We show that this class of graphs lies between Hamiltonian and 1-tough graphs and, surprisingly, that a graph is resistance nonnegative if and only if its twice-dilated matching polytope intersects the interior of its spanning tree polytope. We study further characterizations and basic properties of resistance nonnegative graphs and pose several questions for future research.

Authors: Devriendt, K

• Alternative title: Graphs with Nonnegative Resistance Curvature
• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Annals of Combinatorics
• Volume: 30
• Issue: 2
• Pages: 415-438
• Publication date: 2025-08-06
• Acceptance date: 2025-07-08
• DOI: 10.1007/s00026-025-00774-x
• EISSN: 0219-3094
• ISSN: 0218-0006
• Language: English
• Keywords: Mathematics; Combinatorics; Curvature; Geometry