betaFeedback

WorksMathematics

Resistance-regular graphs need not be regular

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−1m-1 powers of its Laplacian pseudoinverse have constant diagonal, where mm is the number of distinct nonzero Laplacian eigenvalues. Because resistance-regularity constrains only the first power, it forces regularity when m≤2m\le2 and allows at most two vertex degrees when m=3m=3. Any non-regular resistance-regular graph has minimum degree at least 33 and a connected complement, and an exhaustive computer search shows that it must have at least 1313 vertices. For every even p≥4p\ge4, we construct a resistance-regular graph on 4p4p vertices with degrees 2p−22p-2 and 2p−12p-1, obtaining closed formulas for its Laplacian spectrum and for all pairwise effective resistances. Using module blow-ups, we then construct nn-vertex resistance-regular graphs whose two degrees differ by (4n+1−5)/4(\sqrt{4n+1}-5)/4 for infinitely many nn, as well as examples with three and four distinct degrees, whereas the maximum and minimum degrees of any resistance-regular graph on nn vertices differ by less than n/2n/2. We close by conjecturing that in a resistance-regular graph the sum of squared resistances at a vertex increases strictly with its degree.

Introduction

When a connected graph GG is viewed as an electrical network in which every edge is a unit resistor, the effective resistance ruvr_{uv} between two vertices uu and vv is the voltage difference induced when one unit of current enters at uu and leaves at vv. Proposed as a graph metric by Klein and Randić [1], effective resistance connects several parts of combinatorics and probability: it is proportional to the commute time of a simple random walk [2, 3, 4], equals the marginal probability that an edge belongs to a uniformly random spanning tree [5, 6], and underlies spectral sparsification [7], current-flow centrality [8, 9] and recent structural encodings for graph neural networks [10, 11, 12]. Expositions of the general theory can be found in Bapat’s book [13] and the survey of Ellens et al. [14].

Write R=(ruv)R=(r_{uv}) for the resistance matrix of GG, Rv=∑u∼vruvR_v=\sum_{u\sim v}r_{uv} for the resistance degree of a vertex vv, and Kf⁡(G)=12∑vRv\operatorname{Kf}(G)=\frac{1}{2}\sum_v R_v for the Kirchhoff index [1, 15, 16]. Zhou, Wang and Bu [17] called a connected graph resistance-regular if RvR_v is independent of vv. They showed that an nn-vertex connected graph is resistance-regular if and only if the Moore–Penrose inverse L†L^\dagger of its Laplacian LL has constant diagonal, and if and only if the local form of Foster’s theorem [18] holds at every vertex:

∑u∼vruv=2−2nfor all v∈V.\sum_{u\sim v} r_{uv}=2-\frac{2}{n}\qquad\text{for all }v\in V.

Every connected walk-regular graph in the sense of Godsil and McKay [19], and in particular every vertex-transitive or distance-regular graph, is resistance-regular, because regularity makes LL a linear function of the adjacency matrix AA, so that L†L^\dagger is a polynomial in AA and inherits a constant diagonal. Since walk-regular graphs are necessarily regular, Zhou, Wang and Bu asked in [17 Problem 2] whether every resistance-regular graph is regular.

The same question has surfaced independently in work on discrete curvature. Devriendt and Lambiotte [20] defined the resistance curvature of a vertex vv by pv=1−12∑u∼vruvp_v=1-\frac{1}{2}\sum_{u\sim v}r_{uv}. By Foster’s theorem, ∑vpv=1\sum_v p_v=1, so a graph has constant resistance curvature if and only if pv=1/np_v=1/n at every vertex, which is precisely resistance-regularity. Devriendt, Ottolini and Steinerberger [21] developed the theory of this curvature and highlighted the problem of [17]; Haritha and Chithra [22] gave a characterisation of resistance-regular graphs in terms of Laplacian eigenvectors and noted that the literature contained no non-regular example; Sun, Yang and Xu [23] proved that graphs of constant resistance curvature are 2-connected and that, in the normalisation κ=R−11\kappa=R^{-1}\mathbf{1} of [21], the cycle has the smallest constant curvature among them. Resistance curvature in a broader sense is studied in [24], and a related edge-based notion, in which every edge has the same effective resistance, by Palacios [25].

In this paper we show that resistance-regular graphs need not be regular, and we organise our results around three natural questions: what structural and spectral restrictions resistance-regularity imposes, how non-regular examples can be constructed, and how far their degree sequences can depart from regularity.

Recall that a graph is walk-regular if the number of closed walks of each length starting at a vertex does not depend on the vertex. In terms of the local spectral measure of LL at a vertex vv (Definition 2.1), the vertex degree dv=Lvvd_v=L_{vv} is the first positive moment and (L†)vvk(L^\dagger)^k_{vv} is the kk-th negative moment. Resistance-regularity requires only that the first negative moment be constant across all vertices.

Theorem A. Let GG be a connected graph whose Laplacian has mm distinct nonzero eigenvalues.

(i) GG is walk-regular if and only if the diagonal entries of L†L^\dagger, (L†)2,…,(L†)m−1(L^\dagger)^2,\ldots,(L^\dagger)^{m-1} are all constant. In this case the local spectral measure of LL is the same at every vertex, and every power of L†L^\dagger has constant diagonal.

(ii) If GG is resistance-regular and m≤2m\leq2, then GG is walk-regular, and in particular regular. If GG is resistance-regular and m=3m=3, then GG has at most two distinct degrees, and if it has two, they add up to one less than the sum of the three nonzero Laplacian eigenvalues.

(iii) If GG is resistance-regular but not regular, then every vertex of GG has degree at least 3; the complement of GG is connected, so that GG is not the join of two graphs and no vertex of GG is adjacent to all other vertices; and if GG is bipartite, then its two colour classes have the same size.

When m≤2m\leq2, part (i) shows that resistance-regularity alone is strong enough to force walk-regularity, which is the mechanism underlying [17 Theorem 14] (see Corollary 3.2). Once m≥3m\geq3, however, constancy of Lvv†L^\dagger_{vv} imposes only a single linear constraint on the mm weights of the local spectral measure, leaving room for the vertex degree dvd_v to vary. Combined with the 2-connectivity of resistance-regular graphs established by Sun, Yang and Xu [23], the degree and complement restrictions in part (iii) make an exhaustive census of small graphs feasible: no non-regular resistance-regular graph exists on at most 12 vertices, nor on 13 vertices with maximum and minimum degrees differing by at most 2 (Proposition 3.4). Turning to graphs that admit a semiregular automorphism group with two orbits, we found sixteen non-regular examples on 16 to 48 vertices, the smallest of which generalises to an infinite family.

Theorem B. For every even integer p≥4p \ge4 there is a connected graph F(p)\mathcal{F}(p) on 4p4p vertices, with 2p2p vertices of degree 2p−12p-1 and 2p2p vertices of degree 2p−22p-2, in which every vertex has the same resistance degree. Its Laplacian pseudoinverse has diagonal entries (4p2−3p−2)/(8p2(p−2))(4p^2-3p-2)/(8p^2(p-2)), its Laplacian has exactly five distinct nonzero eigenvalues, and every effective resistance in it is one of nine explicit rational functions of pp.

Two of the sporadic 32-vertex examples from the bi-Cayley search have m=4m=4 (Proposition 4.8), showing that resistance-regularity fails to force regularity already for m=4m=4 and m=5m=5, while the case m=3m=3 remains open. A key structural feature of F(p)\mathcal{F}(p) is that its cliques Q0Q_0 and Q1Q_1 are modules, meaning that all vertices in a clique share the exact same neighbours outside it. More generally, when the vertices of a base graph are blown up into cliques, independent sets or arbitrary walk-regular modules, resistance-regularity reduces to a small system of rational equations in the module sizes. Analysing these blow-ups, alongside general Dirichlet and triangle-inequality bounds, yields our third main result.

Theorem C. Let Δ\Delta and δ\delta denote the maximum and minimum degrees of a connected graph GG.

(i) For every integer t≥2t \ge2 there is a connected resistance-regular graph on n=4t2+2tn=4t^2+2t vertices with degrees 2t22t^2 and 2t2+t−12t^2+t-1, so that Δ−δ=(4n+1−5)/4\Delta-\delta=(\sqrt{4n+1}-5)/4.

(ii) There are connected resistance-regular graphs with exactly three and with exactly four distinct degrees.

(iii) Every connected resistance-regular graph on nn vertices satisfies Δ−δ<n/2\Delta-\delta<n/2, and Δ−δ<(2−3)n\Delta-\delta<(2-\sqrt{3})n if it has exactly two distinct degrees.

Thus the largest difference g(n)g(n) between the maximum and the minimum degree of a resistance-regular graph on nn vertices satisfies (4n+1−5)/4≤g(n)<n/2(\sqrt{4n+1}-5)/4 \le g(n)<n/2 for infinitely many nn.

While Theorems B and C show that the row sums of the resistance matrix RR do not determine the vertex degrees, requiring the entire rows of RR to coincide as multisets is far more restrictive. In Section 7 we conjecture that any connected graph whose resistance rows are permutations of one another must be regular (Conjecture 7.2), and we prove that its maximum and minimum degrees can differ by at most one (Proposition 7.4). We also formulate a stronger monotonicity conjecture: in any resistance-regular graph, the second resistance moment ∑rrv2\sum_{r}r_{v}^{2} is a strictly increasing function of the degree dvd_v (Conjecture 7.6). We prove this monotonicity in several cases (Proposition 7.7), verify it across all our examples, and show by a five-vertex counterexample that it fails once edges are allowed to carry unequal weights (Example 7.8). If true in general, Conjecture 7.6 would imply that constancy of the diagonals of both L†L^\dagger and (L†)2(L^\dagger)^2 suffices to force regularity for any mm.

The rest of the paper is organised as follows. Section 2 collects the required background on L†L^\dagger, effective resistance and the Dirichlet lower bounds. Section 3 proves Theorem A and reports the exhaustive census of small graphs up to order 13. Section 4 describes the bi-Cayley search, introduces the family F(p)\mathcal{F}(p) and proves Theorem B. Section 5 develops the general theory of modules and blow-ups, which is then applied in Section 6 to prove Theorem C and relate the degree spread to algebraic connectivity. Section 7 studies the rows and second moments of RR, and Section 8 discusses implications for resistance curvature, network centrality, random spanning trees and distance-based Weisfeiler–Leman tests, concluding with open problems. Appendix A analyses a four-parameter generalisation of F(p)\mathcal{F}(p), and Appendix B lists the explicit connection sets and ancillary verification files.

Preliminaries

Throughout the paper, G=(V,E)G=(V,E) denotes a finite, simple, undirected, connected graph on n=∣V∣≥3n=|V|\ge3 vertices. We write u∼vu\sim v when uu and vv are adjacent, dvd_v for the degree of vv, AA for the adjacency matrix, D=diag⁡(dv)D=\operatorname{diag}(d_v) for the degree matrix, L=D−AL=D-A for the Laplacian, JJ for the n×nn\times n all-ones matrix and 1\mathbf{1} for the all-ones column vector.

Because GG is connected, LL is positive semidefinite with a one-dimensional kernel spanned by 1\mathbf{1}. Its Moore–Penrose inverse L†L^\dagger is the unique symmetric matrix satisfying

LL†=L†L=I−1nJandL†1=0,LL^\dagger=L^\dagger L=I-\frac{1}{n}J \qquad\text{and}\qquad L^\dagger\mathbf{1}=0,

and can be computed as L†=(L+J/n)−1−J/nL^\dagger=(L+J/n)^{-1}-J/n [13]. Let μ1<μ2<⋯<μm\mu_1<\mu_2<\cdots<\mu_m be the distinct nonzero eigenvalues of LL, and let E1,…,EmE_1,\ldots,E_m be the orthogonal projections onto the corresponding eigenspaces. Then

L=∑i=1mμiEi,L†=∑i=1mμi−1Ei,∑i=1mEi=I−1nJ.L=\sum_{i=1}^{m}\mu_iE_i,\qquad L^\dagger=\sum_{i=1}^{m}\mu_i^{-1}E_i,\qquad\sum_{i=1}^{m}E_i=I-\frac{1}{n}J.

Definition 2.1 (local spectral measure). For a vertex v∈Vv\in V, the nonnegative numbers ei(v)=(Ei)vve_i(v)=(E_i)_{vv}, i=1,…,mi=1,\ldots,m, form the local spectral measure of LL at vv. They satisfy ∑i=1mei(v)=1−1/n\sum_{i=1}^{m}e_i(v)=1-1/n, and (Lk)vv=∑i=1mμikei(v)(L^k)_{vv}=\sum_{i=1}^{m}\mu_i^k e_i(v) and ((L†)k)vv=∑i=1mμi−kei(v)((L^\dagger)^k)_{vv}=\sum_{i=1}^{m}\mu_i^{-k}e_i(v) for every integer k≥1k\ge1.

Definition 2.2 (effective resistance, resistance degree, Kirchhoff index). The effective resistance between vertices uu and vv is

ruv=Luu†+Lvv†−2Luv†,(1)r_{uv}=L^\dagger_{uu}+L^\dagger_{vv}-2L^\dagger_{uv}, \tag*{(1)}

the energy dissipated by a unit current flowing from uu to vv when every edge is a unit resistor. The matrix R=(ruv)R=(r_{uv}) is the resistance matrix, the resistance degree of vv is Rv=∑u∈VruvR_v=\sum_{u\in V}r_{uv}, and the Kirchhoff index is Kf⁡(G)=12∑v∈VRv\operatorname{Kf}(G)=\frac{1}{2}\sum_{v\in V}R_v.

Effective resistance is a metric on VV [1, 13]. Summing (1) over u∈Vu\in V and using L†1=0L^\dagger\mathbf{1}=0 relates RvR_v to the diagonal entry Lvv†L^\dagger_{vv}:

References

  1. [1]D. J. Klein and M. Randić, “Resistance distance,” Journal of Mathematical Chemistry, vol. 12, pp. 81–95, 1993.DOI
  2. [2]A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari, “The electrical resistance of a graph captures its commute and cover times,” in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 574–586, 1989.
  3. [3]P. Tetali, “Random walks and the effective resistance of networks,” Journal of Theoretical Probability, vol. 4, pp. 101–109, 1991.DOI
  4. [4]L. Lovász, “Random walks on graphs: a survey,” in Combinatorics, Paul Erdős is Eighty, vol. 2 of Bolyai Society Mathematical Studies, pp. 353–397, János Bolyai Mathematical Society, 1993.
  5. [5]G. Kirchhoff, “Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird,” Annalen der Physik und Chemie, vol. 72, pp. 497–508, 1847.DOI
  6. [6]P. G. Doyle and J. L. Snell, Random Walks and Electric Networks, vol. 22 of Carus Mathematical Monographs. Mathematical Association of America, 1984.
  7. [7]D. A. Spielman and N. Srivastava, “Graph sparsification by effective resistances,” SIAM Journal on Computing, vol. 40, pp. 1913–1926, 2011.
  8. [8]K. Stephenson and M. Zelen, “Rethinking centrality: methods and examples,” Social Networks, vol. 11, pp. 1–37, 1989.DOI
  9. [9]U. Brandes and D. Fleischer, “Centrality measures based on current flow,” in Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005), vol. 3404 of Lecture Notes in Computer Science, pp. 533–544, Springer, 2005.DOI
  10. [10]B. Zhang, S. Luo, L. Wang, and D. He, “Rethinking the expressive power of GNNs via graph biconnectivity,” in International Conference on Learning Representations (ICLR), 2023.arxiv.org/abs/2301.09505
  11. [11]M. Black, Z. Wan, A. Nayyeri, and Y. Wang, “Understanding oversquashing in GNNs through the lens of effective resistance,” in Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.arxiv.org/abs/2302.06835
  12. [12]M. Black, Z. Wan, G. Mishne, A. Nayyeri, and Y. Wang, “Comparing graph transformers via positional encodings,” in Proceedings of the 41st International Conference on Machine Learning (ICML), 2024.arxiv.org/abs/2402.14202
  13. [13]R. B. Bapat, Graphs and Matrices. London: Springer, 2nd ed., 2014.
  14. [14]W. Ellens, F. M. Spieksma, P. Van Mieghem, A. Jamakovic, and R. E. Kooij, “Effective graph resistance,” Linear Algebra and its Applications, vol. 435, pp. 2491–2506, 2011.DOI
  15. [15]R. B. Bapat, I. Gutman, and W. Xiao, “A simple method for computing resistance distance,” Zeitschrift für Naturforschung A, vol. 58, pp. 494–498, 2003.DOI
  16. [16]R. B. Bapat, “Resistance matrix of a weighted graph,” MATCH Communications in Mathematical and in Computer Chemistry, vol. 50, pp. 73–82, 2004.
  17. [17]J. Zhou, Z. Wang, and C. Bu, “On the resistance matrix of a graph,” The Electronic Journal of Combinatorics, vol. 23, no. 1, p. P1.41, 2016.DOI
  18. [18]R. M. Foster, “The average impedance of an electrical network,” Contributions to Applied Mechanics (Reissner Anniversary Volume), pp. 333–340, 1949.
  19. [19]C. D. Godsil and B. D. McKay, “Feasibility conditions for the existence of walk-regular graphs,” Linear Algebra and its Applications, vol. 30, pp. 51–61, 1980.DOI
  20. [20]K. Devriendt and R. Lambionette, “Discrete curvature on graphs from the effective resistance,” Journal of Physics: Complexity, vol. 3, p. 025008, 2022.DOI
  21. [21]K. Devriendt, A. Ottolini, and S. Steinerberger, “Graph curvature via resistance distance,” Discrete Applied Mathematics, vol. 348, pp. 68–78, 2024.arxiv.org/abs/2302.06021
  22. [22]T. Haritha and A. V. Chithra, “On the resistance regular graphs,” 2025. arXiv:2405.18177v3 (first version 2024).arxiv.org/abs/2405.18177
  23. [23]W. Sun, Y. Yang, and S.-J. Xu, “On the minimum constant resistance curvature conjecture of graphs,” Discrete Applied Mathematics, 2026. doi:10.1016/j.dam.2026.03.027; arXiv:2504.20448.DOI
  24. [24]M. Guo, W. Sun, and Y. Yang, “Resistance curvature: recognition, polyhedral structure, and graph products,” 2026. arXiv:2608.20778.arxiv.org/abs/2608.20778
  25. [25]J. L. Palacios, “On equire­sistant graphs,” Mathematics, vol. 14, no. 5, p. 798, 2026.
  26. [26]B. Mohar, “The Laplacian spectrum of graphs,” in Graph Theory, Combinatorics, and Applications, vol. 2, pp. 871–898, Wiley, 1991.
  27. [27]C. Godsil and G. Royle, Algebraic Graph Theory, vol. 207 of Graduate Texts in Mathematics. New York: Springer, 2001.DOI
  28. [28]B. D. McKay and A. Piperno, “Practical graph isomorphism, II,” Journal of Symbolic Computation, vol. 60, pp. 94–112, 2014.
  29. [29]M. Fiedler, “Algebraic connectivity of graphs,” Czechoslovak Mathematical Journal, vol. 23, no. 2, pp. 298–305, 1973.DOI
  30. [30]N. J. Higham, Accuracy and Stability of Numerical Algorithms. Philadelphia: SIAM, second ed., 2002.
  31. [31]OEIS Foundation Inc., “The on-line encyclopedia of integer sequences,” 2026. Sequence A002218, https://oeis.org/A002218.
  32. [32]J.-X. Zhou and Y.-Q. Feng, “The automorphisms of bi-Cayley graphs,” Journal of Combinatorial Theory, Series B, vol. 116, pp. 504–532, 2016.DOI
  33. [33]X. Gao and Y. Luo, “The spectrum of semi-Cayley graphs over abelian groups,” Linear Algebra and its Applications, vol. 432, pp. 2974–2983, 2010.DOI
  34. [34]A. Azimi, R. B. Bapat, and M. Farrokhi, “Resistance distance of blowups of trees,” Discrete Mathematics, vol. 344, no. 7, p. 112387, 2021. doi:10.1016/j.disc.2021.112387.DOI
  35. [35]H. Liu, L. Li, L. You, H. Hua, and L. Chen, “Enumeration of spanning trees and resistance distances of generalized blow-up graphs,” 2025. arXiv:2504.15314.arxiv.org/abs/2504.15314
  36. [36]J. Flora, M. Black, W.-K. Wong, and A. Nayveri, “Understanding truncated positional encodings for graph neural networks,” in Proceedings of the 43rd International Conference on Machine Learning (ICML), vol. 306 of Proceedings of Machine Learning Research, pp. 31161–31188, 2026. arXiv:2606.13671.arxiv.org/abs/2606.13671

Paper details

vlnc:W_6yd274bw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents