TOPICS
Search

Resistance-Regular Graph


A resistance-regular graph is a finite connected simple graph for which sum_(u)r_(vu) is independent of the graph vertex v, where r_(vu) is resistance distance with each graph edge a unit resistor (Zhou et al. 2016). Equivalently, the Moore-Penrose matrix inverse L^| of its Laplacian matrix has constant diagonal. Every connected walk-regular graph, and hence every connected vertex-transitive graph, is resistance-regular. Resistance-regularity also means that each vertex has expected degree 2(n-1)/n in a uniformly chosen spanning tree.

Khan and Haidar (2026) show that resistance-regular graphs need not be regular graphs. For every even p>=4, they construct a graph F(p) on 4p vertices, half of degree 2p-1 and half of degree 2p-2, with common diagonal entry

 L_(vv)^|=(4p^2-3p-2)/(8p^2(p-2)).

For F(4), there are 16 vertices and 52 edges, and L_(vv)^|=25/128. To construct F(p), take disjoint p-vertex cliques Q_0,Q_1 and sets X_b={x_(b,c,t):c=0,1; 0<=t<p/2}. Completely join Q_b to X_b. For each c, make the p vertices x_(b,c,t) into a cocktail party graph by omitting just the matching pairs {x_(0,c,t),x_(1,c,t)}; add no other edges. The authors' computer-assisted enumeration excludes nonregular resistance-regular graphs on at most 12 vertices, leaving the minimum order between 13 and 16. The enumeration uses floating-point filters with stated backward-error bounds, followed by exact checks.

Any nonregular resistance-regular graph has minimum degree at least 3 and connected graph complement; if bipartite, its two vertex parts have equal size. If L has at most two distinct nonzero eigenvalues, resistance-regularity forces walk-regularity. With three distinct nonzero eigenvalues, at most two vertex degrees occur; nonregular examples with four such eigenvalues exist, while the three-eigenvalue case remains open (Khan and Haidar 2026).

For every integer t>=2, Khan and Haidar (2026) construct a resistance-regular graph on n=4t^2+2t vertices whose degrees are 2t^2 and 2t^2+t-1. It is the blow-up of a six-cycle with opposite vertices replaced by independent sets of size t and the other four by cliques of size t^2, with complete joins between consecutive parts. They also give examples with exactly three and exactly four distinct degrees. For every resistance-regular graph, the maximum and minimum degrees satisfy Delta-delta<n/2, improved to (2-sqrt(3))n when exactly two degrees occur. With algebraic connectivity lambda_2, they additionally satisfy (Delta-delta)(n-2)lambda_2<=delta(n-Delta). If the full resistance rows are equal as multisets, the stronger restriction Delta-delta<=1 holds; whether such a graph must be regular remains open. The authors report that Claude assisted with the computational search scripts.


See also

Laplacian Matrix, Resistance Distance, Walk-Regular Graph

Explore with Wolfram|Alpha

References

Zhou, J.; Wang, Z.; and Bu, C. "On the Resistance Matrix of a Graph." Elec. J. Combin. 23, P1.41, 2016.Khan, M. ul I. and Haidar, G. "Resistance-Regular Graphs Need Not Be Regular." 12 Nov 2026. https://arxiv.org/abs/2611.21670v1.

Cite this as:

Weisstein, Eric W. "Resistance-Regular Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Resistance-RegularGraph.html

Subject classifications