Scholarlink

<p>This article introduces and studies a new class of graphs motivated by discrete curvature. We call a graph <i>resistance nonnegative</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Graphs with Nonnegative Resistance Curvature

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月6日

查看全文
  • Karel Devriendt

摘要

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.