Paperlane

no. 17 · Wednesday 18 November 2026

Resistance-regular graphs need not be regular

Murad ul Islam Khan and Ghulam Haidar

math.CO

Abstract

A connected graph is resistance-regular if the sum of the effective resistances from a vertex to all other vertices does not depend on the vertex, or equivalently if the Moore-Penrose inverse of its Laplacian has constant diagonal. Walk-regular graphs have this property, and Zhou, Wang and Bu asked in 2016 whether every resistance-regular graph is regular, a question that also arises in the study of graphs with constant resistance curvature. We answer this question in the negative and examine both what resistance-regularity forces and how far from regular such graphs can be. On the spectral side, we prove that a connected graph is walk-regular if and only if the first $m-1$ powers of its Laplacian pseudoinverse have constant diagonal, where $m$ is the number of distinct nonzero Laplacian eigenvalues. Because resistance-regularity constrains only the first power, it forces regularity when $m\le2$ and allows at most two vertex degrees when $m=3$. Any non-regular resistance-regular graph has minimum degree at least $3$ and a connected complement, and an exhaustive computer search shows that it must have at least $13$ vertices. For every even $p\ge4$, we construct a resistance-regular graph on $4p$ vertices with degrees $2p-2$ and $2p-1$, obtaining closed formulas for its Laplacian spectrum and for all pairwise effective resistances. Using module blow-ups, we then construct $n$-vertex resistance-regular graphs whose two degrees differ by $(\sqrt{4n+1}-5)/4$ for infinitely many $n$, as well as examples with three and four distinct degrees, whereas the maximum and minimum degrees of any resistance-regular graph on $n$ vertices differ by less than $n/2$. We close by conjecturing that in a resistance-regular graph the sum of squared resistances at a vertex increases strictly with its degree.

fields
Combinatorics
pdf ↗ page arXiv:2611.21670 ↗