Graphs with nonnegative resistance curvature
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916884527448064 |
|---|---|
| author | Devriendt, Karel |
| author_facet | Devriendt, Karel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_07756 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graphs with nonnegative resistance curvature Devriendt, Karel Combinatorics Discrete Mathematics Metric Geometry 05C75, 05C05, 52B05, 05C42, 05C45, 52B40 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. |
| title | Graphs with nonnegative resistance curvature |
| topic | Combinatorics Discrete Mathematics Metric Geometry 05C75, 05C05, 52B05, 05C42, 05C45, 52B40 |
| url | https://arxiv.org/abs/2410.07756 |