A resistance-regular graph is a finite connected simple graph for which is independent of the graph
vertex
, where
is resistance distance
with each graph edge a unit resistor (Zhou et al.
2016). Equivalently, the Moore-Penrose
matrix inverse
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
in a uniformly chosen spanning
tree.
Khan and Haidar (2026) show that resistance-regular graphs need not be regular graphs. For every even ,
they construct a graph
on
vertices, half of degree
and half of degree
,
with common diagonal entry
For , there are 16 vertices and 52 edges, and
. To construct
, take disjoint
-vertex cliques
and sets
.
Completely join
to
.
For each
, make the
vertices
into a cocktail
party graph by omitting just the matching pairs
; 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 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 ,
Khan and Haidar (2026) construct a resistance-regular graph on
vertices whose degrees are
and
.
It is the blow-up of a six-cycle with opposite vertices replaced by independent
sets of size
and the other four by cliques of size
, 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
, improved to
when exactly two degrees occur. With algebraic
connectivity
,
they additionally satisfy
.
If the full resistance rows are equal as multisets, the stronger restriction
holds; whether such a graph must be regular remains open. The authors report that
Claude assisted with the computational search scripts.