Metraipolis › archive › dc_eba39377ddf9
Resistance Curvature: Recognition, Polyhedral Structure, and Graph Products — arXiv:2608.20778
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.20778
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T10:46:55.864Z
- SHA-256 of the archived text
0cb3a185b537547a6b271aafcc3b442994090c452c744f628795134b58fed149- Stable URL of this page
https://metraipolis.com/documento/dc_eba39377ddf9
How to cite
Resistance Curvature: Recognition, Polyhedral Structure, and Graph Products — arXiv:2608.20778 — arXiv (en), https://arxiv.org/abs/2608.20778 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eba39377ddf9 (Metraipolis archive dc_eba39377ddf9, sha256 0cb3a185b537547a6b271aafcc3b442994090c452c744f628795134b58fed149)
BibTeX
@misc{dceba39377ddf9,
title = {Resistance Curvature: Recognition, Polyhedral Structure, and Graph Products — arXiv:2608.20778},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.20778},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eba39377ddf9; sha256 0cb3a185b537547a6b271aafcc3b442994090c452c744f628795134b58fed149},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.20778. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Resistance curvature, introduced by Devriendt and Lambiotte, is a novel discrete curvature notion defined through effective resistance. A graph is called resistance nonnegative if there exists a choice of positive edge weights for which the resistance curvature is nonnegative at every vertex. This property has a notable combinatorial interpretation in terms of random spanning trees: a graph is resistance nonnegative if and only if it admits a distribution on its spanning trees under which every vertex has expected degree at most two. The resistance nonnegativity can also be characterized by the tree double matching polytope. These characterizations reveal strong connections among resistance curvature, effective resistance, spanning tree distributions, matching theory, and polyhedral combinatorics. Based on the sign of the curvature, Devriendt introduced the classes of resistance nonnegative (RN), resistance positive (RP), and strictly resistance nonnegative (SRN) graphs, and posed several questions concerning their recognition, polyhedral structure, and structural properties. In this paper, we first answer Devriendt's question on the computational complexity of recognizing RN, RP, and SRN graphs by proving that all three classes can be recognized in polynomial time. We then address his question concerning the tree double matching polytope $\Theta(G)$. Further, we characterize the vertices of $\Theta(G)$ in terms of full-rank systems of tight constraints. Whenever $\Theta(G)\neq\emptyset$, we also determine the least positive integer $k_G$ such that $k_G\Theta(G)$ is a lattice polytope. Finally, for every finite Cartesian product of paths, we explicitly construct an average point satisfying the condition for resistance nonnegativity, thereby obtaining that such graphs are RN. We further characterize the classes of such Cartesian product graphs that are RP or SRN. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-24 in math.CO). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2608.20778 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-18T10:39:26.740Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-24?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).