2024/10/10 by Karel Devriendt, Devriendt, Karel · 1 citation
Computer Science · Engineering · #05C05 #05C42 #05C45 #05C75 #52B05 #52B40 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Structural Analysis and Optimization
paper · pdf · doi:10.48550/arxiv.2410.07756
openalex publication_date 2024/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.