Resistance Curvature Separates Toughness From Traceability

Resistance curvature is a graph invariant built from effective resistance: edge weights induce relative edge resistances, and a vertex has nonnegative curvature when the incident relative resistances average to at most 2. Devriendt’s recent characterization connected this condition to distributions over spanning trees, suggesting a close relation between resistance-positive graphs, Hamiltonian structure, and graph toughness. This paper shows that the relation is real but much looser than the existing containments suggested.

The authors study two classes. A graph is resistance nonnegative, or RN, if some positive edge weighting gives $p_v(c) \geq 0$ at every vertex; it is resistance positive, or RP, if all those inequalities are strict. Before this work, known results placed Hamiltonian graphs inside RP graphs and RP graphs inside 1-tough graphs. The paper’s contribution is to draw sharper boundaries around those containments.

Core Contribution

The main finding is a set of separations and one positive closure theorem. First, the paper disproves a conjecture attributed to Fiedler and answers Devriendt’s question by constructing, for every $n \geq 11$, an $n$-vertex graph that is 1-tough but not RN. Since non-RN also means non-RP, toughness alone cannot force nonnegative resistance curvature.

Second, the authors prove that RP does not imply even traceability. The witness is the Thomassen 34-graph $T_{34}$, already known to be hypotraceable: $T_{34}$ itself has no Hamiltonian path, but deleting any vertex makes it traceable. The paper supplies a curvature certificate showing that $T_{34}$ is RP.

Third, the paper resolves Devriendt’s grid-graph conjecture in the affirmative. For all positive integers $d,n_1,\ldots,n_d$, the Cartesian product $P_{n_1}\times\cdots\times P_{n_d}$ is RN. This covers grids in any dimension, including products of more than two paths.

Technical Approach

For the grid result, the authors introduce a sufficient condition called a sprawling set: a collection of Hamiltonian paths that covers every edge and violates induced spanning-tree behavior on every connected proper induced subgraph. They prove every sprawling graph is RN, then construct such path families for Cartesian products of paths by recursively sweeping coordinate lines.

Results and Analysis

The evidence is proof-based rather than experimental. The 1-tough construction is the cleanest separation: it applies uniformly to every $n\geq 11$, not just to a sporadic counterexample. It directly breaks the hoped-for implication from toughness to RN and shows the known containment RP $\subseteq$ 1-tough is not reversible.

The Thomassen-graph result is narrower but useful. The proof labels edges with three values, $a=33/68$, $b=99/136$, and $c=165/272$, then verifies the spanning-tree-polytope inequalities and obtains $x(E(v))=33/17<2$ for every vertex. A computer search is used to verify that certain cuts have at least four edges, so the certificate is partly computational but still tied to explicit rational weights. The result separates RP from traceability, a weaker Hamiltonian-type property than Hamiltonicity.

The positive theorem for path products is less about finding new individual RN graphs than about giving a reusable combinatorial certificate. The sprawling-set condition is sufficient, not necessary: the paper itself gives examples of RN or RP graphs that are not sprawling. That limits the characterization value of the framework, but it still resolves the stated path-product conjecture and explains why grid graphs admit the needed spanning-tree distributions.