Introduction
When a connected graph G G G is viewed as an electrical network in which every edge is a unit resistor, the effective resistance r u v r_{uv} r uv between two vertices u u u and v v v is the voltage difference induced when one unit of current enters at u u u and leaves at v v v . 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 = ( r u v ) R=(r_{uv}) R = ( r uv ) for the resistance matrix of G G G , R v = ∑ u ∼ v r u v R_v=\sum_{u\sim v}r_{uv} R v = ∑ u ∼ v r uv for the resistance degree of a vertex v v v , and Kf ( G ) = 1 2 ∑ v R v \operatorname{Kf}(G)=\frac{1}{2}\sum_v R_v Kf ( G ) = 2 1 ∑ v R v for the Kirchhoff index [1 , 15 , 16 ] . Zhou, Wang and Bu [17 ] called a connected graph resistance-regular if R v R_v R v is independent of v v v . They showed that an n n n -vertex connected graph is resistance-regular if and only if the Moore–Penrose inverse L † L^\dagger L † of its Laplacian L L L has constant diagonal, and if and only if the local form of Foster’s theorem [18 ] holds at every vertex:
∑ u ∼ v r u v = 2 − 2 n for all v ∈ V . \sum_{u\sim v} r_{uv}=2-\frac{2}{n}\qquad\text{for all }v\in V. u ∼ v ∑ r uv = 2 − n 2 for all v ∈ 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 L L L a linear function of the adjacency matrix A A A , so that L † L^\dagger L † is a polynomial in A A A 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 v v v by p v = 1 − 1 2 ∑ u ∼ v r u v p_v=1-\frac{1}{2}\sum_{u\sim v}r_{uv} p v = 1 − 2 1 ∑ u ∼ v r uv . By Foster’s theorem, ∑ v p v = 1 \sum_v p_v=1 ∑ v p v = 1 , so a graph has constant resistance curvature if and only if p v = 1 / n p_v=1/n p 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 − 1 1 \kappa=R^{-1}\mathbf{1} κ = R − 1 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 L L L at a vertex v v v (Definition 2.1), the vertex degree d v = L v v d_v=L_{vv} d v = L v v is the first positive moment and ( L † ) v v k (L^\dagger)^k_{vv} ( L † ) v v k is the k k k -th negative moment. Resistance-regularity requires only that the first negative moment be constant across all vertices.
Theorem A. Let G G G be a connected graph whose Laplacian has m m m distinct nonzero eigenvalues.
(i) G G G is walk-regular if and only if the diagonal entries of L † L^\dagger L † , ( L † ) 2 , … , ( L † ) m − 1 (L^\dagger)^2,\ldots,(L^\dagger)^{m-1} ( L † ) 2 , … , ( L † ) m − 1 are all constant. In this case the local spectral measure of L L L is the same at every vertex, and every power of L † L^\dagger L † has constant diagonal.
(ii) If G G G is resistance-regular and m ≤ 2 m\leq2 m ≤ 2 , then G G G is walk-regular, and in particular regular. If G G G is resistance-regular and m = 3 m=3 m = 3 , then G G G 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 G G G is resistance-regular but not regular, then every vertex of G G G has degree at least 3; the complement of G G G is connected, so that G G G is not the join of two graphs and no vertex of G G G is adjacent to all other vertices; and if G G G is bipartite, then its two colour classes have the same size.
When m ≤ 2 m\leq2 m ≤ 2 , 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 ≥ 3 m\geq3 m ≥ 3 , however, constancy of L v v † L^\dagger_{vv} L v v † imposes only a single linear constraint on the m m m weights of the local spectral measure, leaving room for the vertex degree d v d_v d 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 ≥ 4 p \ge4 p ≥ 4 there is a connected graph F ( p ) \mathcal{F}(p) F ( p ) on 4 p 4p 4 p vertices, with 2 p 2p 2 p vertices of degree 2 p − 1 2p-1 2 p − 1 and 2 p 2p 2 p vertices of degree 2 p − 2 2p-2 2 p − 2 , in which every vertex has the same resistance degree. Its Laplacian pseudoinverse has diagonal entries ( 4 p 2 − 3 p − 2 ) / ( 8 p 2 ( p − 2 ) ) (4p^2-3p-2)/(8p^2(p-2)) ( 4 p 2 − 3 p − 2 ) / ( 8 p 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 p p p .
Two of the sporadic 32-vertex examples from the bi-Cayley search have m = 4 m=4 m = 4 (Proposition 4.8 ), showing that resistance-regularity fails to force regularity already for m = 4 m=4 m = 4 and m = 5 m=5 m = 5 , while the case m = 3 m=3 m = 3 remains open. A key structural feature of F ( p ) \mathcal{F}(p) F ( p ) is that its cliques Q 0 Q_0 Q 0 and Q 1 Q_1 Q 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 G G G .
(i) For every integer t ≥ 2 t \ge2 t ≥ 2 there is a connected resistance-regular graph on n = 4 t 2 + 2 t n=4t^2+2t n = 4 t 2 + 2 t vertices with degrees 2 t 2 2t^2 2 t 2 and 2 t 2 + t − 1 2t^2+t-1 2 t 2 + t − 1 , so that Δ − δ = ( 4 n + 1 − 5 ) / 4 \Delta-\delta=(\sqrt{4n+1}-5)/4 Δ − δ = ( 4 n + 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 n n n vertices satisfies Δ − δ < n / 2 \Delta-\delta<n/2 Δ − δ < n /2 , and Δ − δ < ( 2 − 3 ) n \Delta-\delta<(2-\sqrt{3})n Δ − δ < ( 2 − 3 ) n if it has exactly two distinct degrees.
Thus the largest difference g ( n ) g(n) g ( n ) between the maximum and the minimum degree of a resistance-regular graph on n n n vertices satisfies ( 4 n + 1 − 5 ) / 4 ≤ g ( n ) < n / 2 (\sqrt{4n+1}-5)/4 \le g(n)<n/2 ( 4 n + 1 − 5 ) /4 ≤ g ( n ) < n /2 for infinitely many n n n .
While Theorems B and C show that the row sums of the resistance matrix R R R do not determine the vertex degrees, requiring the entire rows of R R R 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 ∑ r r v 2 \sum_{r}r_{v}^{2} ∑ r r v 2 is a strictly increasing function of the degree d v d_v d 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 L † and ( L † ) 2 (L^\dagger)^2 ( L † ) 2 suffices to force regularity for any m m m .
The rest of the paper is organised as follows. Section 2 collects the required background on L † L^\dagger L † , 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) 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 R R R , 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) F ( p ) , and Appendix B lists the explicit connection sets and ancillary verification files.
Preliminaries
Throughout the paper, G = ( V , E ) G=(V,E) G = ( V , E ) denotes a finite, simple, undirected, connected graph on n = ∣ V ∣ ≥ 3 n=|V|\ge3 n = ∣ V ∣ ≥ 3 vertices. We write u ∼ v u\sim v u ∼ v when u u u and v v v are adjacent, d v d_v d v for the degree of v v v , A A A for the adjacency matrix, D = diag ( d v ) D=\operatorname{diag}(d_v) D = diag ( d v ) for the degree matrix, L = D − A L=D-A L = D − A for the Laplacian, J J J for the n × n n\times n n × n all-ones matrix and 1 \mathbf{1} 1 for the all-ones column vector.
Because G G G is connected, L L L is positive semidefinite with a one-dimensional kernel spanned by 1 \mathbf{1} 1 . Its Moore–Penrose inverse L † L^\dagger L † is the unique symmetric matrix satisfying
L L † = L † L = I − 1 n J and L † 1 = 0 , LL^\dagger=L^\dagger L=I-\frac{1}{n}J \qquad\text{and}\qquad L^\dagger\mathbf{1}=0, L L † = L † L = I − n 1 J and L † 1 = 0 ,
and can be computed as L † = ( L + J / n ) − 1 − J / n L^\dagger=(L+J/n)^{-1}-J/n L † = ( L + J / n ) − 1 − J / n [13 ] . Let μ 1 < μ 2 < ⋯ < μ m \mu_1<\mu_2<\cdots<\mu_m μ 1 < μ 2 < ⋯ < μ m be the distinct nonzero eigenvalues of L L L , and let E 1 , … , E m E_1,\ldots,E_m E 1 , … , E m be the orthogonal projections onto the corresponding eigenspaces. Then
L = ∑ i = 1 m μ i E i , L † = ∑ i = 1 m μ i − 1 E i , ∑ i = 1 m E i = I − 1 n J . 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. L = i = 1 ∑ m μ i E i , L † = i = 1 ∑ m μ i − 1 E i , i = 1 ∑ m E i = I − n 1 J .
Definition 2.1 (local spectral measure). For a vertex v ∈ V v\in V v ∈ V , the nonnegative numbers e i ( v ) = ( E i ) v v e_i(v)=(E_i)_{vv} e i ( v ) = ( E i ) v v , i = 1 , … , m i=1,\ldots,m i = 1 , … , m , form the local spectral measure of L L L at v v v . They satisfy ∑ i = 1 m e i ( v ) = 1 − 1 / n \sum_{i=1}^{m}e_i(v)=1-1/n ∑ i = 1 m e i ( v ) = 1 − 1/ n , and ( L k ) v v = ∑ i = 1 m μ i k e i ( v ) (L^k)_{vv}=\sum_{i=1}^{m}\mu_i^k e_i(v) ( L k ) v v = ∑ i = 1 m μ i k e i ( v ) and ( ( L † ) k ) v v = ∑ i = 1 m μ i − k e i ( v ) ((L^\dagger)^k)_{vv}=\sum_{i=1}^{m}\mu_i^{-k}e_i(v) (( L † ) k ) v v = ∑ i = 1 m μ i − k e i ( v ) for every integer k ≥ 1 k\ge1 k ≥ 1 .
Definition 2.2 (effective resistance, resistance degree, Kirchhoff index). The effective resistance between vertices u u u and v v v is
r u v = L u u † + L v v † − 2 L u v † , (1) r_{uv}=L^\dagger_{uu}+L^\dagger_{vv}-2L^\dagger_{uv}, \tag*{(1)} r uv = L uu † + L v v † − 2 L uv † , (1)
the energy dissipated by a unit current flowing from u u u to v v v when every edge is a unit resistor. The matrix R = ( r u v ) R=(r_{uv}) R = ( r uv ) is the resistance matrix , the resistance degree of v v v is R v = ∑ u ∈ V r u v R_v=\sum_{u\in V}r_{uv} R v = ∑ u ∈ V r uv , and the Kirchhoff index is Kf ( G ) = 1 2 ∑ v ∈ V R v \operatorname{Kf}(G)=\frac{1}{2}\sum_{v\in V}R_v Kf ( G ) = 2 1 ∑ v ∈ V R v .
Effective resistance is a metric on V V V [1 , 13 ] . Summing (1) over u ∈ V u\in V u ∈ V and using L † 1 = 0 L^\dagger\mathbf{1}=0 L † 1 = 0 relates R v R_v R v to the diagonal entry L v v † L^\dagger_{vv} L v v † :
R v = n L v v † + tr L † . (2) R_v=nL^\dagger_{vv}+\operatorname{tr}L^\dagger. \tag*{(2)} R v = n L v v † + tr L † . (2)
In particular Kf ( G ) = n tr L † \operatorname{Kf}(G)=n\operatorname{tr}L^\dagger Kf ( G ) = n tr L † . By Kirchhoff’s theorem [5 , 6 ] , the effective resistance across an edge u v ∈ E uv\in E uv ∈ E equals
r u v = τ u v τ ( u v ∈ E ) , (3) r_{uv}=\frac{\tau_{uv}}{\tau}\qquad(uv\in E), \tag*{(3)} r uv = τ τ uv ( uv ∈ E ) , (3)
where τ \tau τ is the number of spanning trees of G G G and τ u v \tau_{uv} τ uv is the number of spanning trees containing the edge u v uv uv . Summing (3) over all edges yields Foster’s identity ∑ u v ∈ E r u v = n − 1 \sum_{uv\in E}r_{uv}=n-1 ∑ uv ∈ E r uv = n − 1 [18 ] , reflecting the fact that every spanning tree has n − 1 n-1 n − 1 edges.
Definition 2.3 (resistance-regular graph). A connected graph G G G is resistance-regular if the resistance degree R v R_v R v is the same for all v ∈ V v\in V v ∈ V .
We collect the basic characterisations of resistance-regularity from [17 ] .
Theorem 2.4 ([17 Theorem 12] ). For a connected graph G G G on n n n vertices, the following are equivalent:
(i) G G G is resistance-regular;
(ii) the diagonal entries of L † L^{\dagger} L † are all equal;
(iii) ∑ u ∼ v r u v = 2 − 2 / n \sum_{u\sim v} r_{uv}=2-2/n ∑ u ∼ v r uv = 2 − 2/ n for every vertex v ∈ V v\in V v ∈ V ;
(iv) the eigenvalues of the resistance matrix R R R are 2 Kf ( G ) / n 2\operatorname{Kf}(G)/n 2 Kf ( G ) / n and − 2 / μ -2/\mu − 2/ μ , where μ \mu μ runs over the nonzero eigenvalues of L L L with multiplicity.
The equivalence of (i) and (ii) is immediate from (2) , while condition (iii) states via (3) that every vertex has the same expected degree 2 ( n − 1 ) / n 2(n-1)/n 2 ( n − 1 ) / n in a uniformly random spanning tree. Condition (iii) also implies two simple structural restrictions that are useful when searching for examples.
Proposition 2.5. Let G G G be a resistance-regular graph on n ≥ 3 n\geq3 n ≥ 3 vertices with τ \tau τ spanning trees. Then G G G is 2-connected, and n n n divides 2 τ 2\tau 2 τ .
Proof. A vertex v v v of degree one would be incident to a single bridge u v uv uv , which lies in every spanning tree and therefore has r u v = 1 r_{uv}=1 r uv = 1 ; this contradicts Theorem 2.4 (iii) since 2 − 2 / n > 1 2-2/n>1 2 − 2/ n > 1 for n ≥ 3 n\geq3 n ≥ 3 . That G G G has no cut vertex at all is Theorem 2.5 of [23 ] , proved there in the language of constant resistance curvature. For the divisibility condition, multiplying Theorem 2.4 (iii) by τ \tau τ and applying (3) gives ∑ u ∼ v τ u v = 2 τ ( n − 1 ) / n \sum_{u\sim v}\tau_{uv}=2\tau(n-1)/n ∑ u ∼ v τ uv = 2 τ ( n − 1 ) / n . The left-hand side is an integer, and since gcd ( n , n − 1 ) = 1 \gcd(n,n-1)=1 g cd( n , n − 1 ) = 1 , n n n must divide 2 τ 2\tau 2 τ .
Definition 2.6 (walk-regular graph). A graph G G G is walk-regular [19 ] if, for every integer k ≥ 0 k\geq0 k ≥ 0 , the number of closed walks of length k k k starting at v v v , namely ( A k ) v v (A^k)_{vv} ( A k ) v v , does not depend on v v v .
Taking k = 2 k=2 k = 2 shows that every walk-regular graph is regular. If G G G is connected and walk-regular of degree d d d , then L = d I − A L=dI-A L = d I − A and L † L^{\dagger} L † is a polynomial in A A A , so L v v † L^{\dagger}_{vv} L v v † is independent of v v v and G G G is resistance-regular [17 Remark 2] .
Bounds on effective resistance
We shall repeatedly use the following elementary lower bounds, which depend only on the degrees of the two vertices.
Lemma 2.7 (Dirichlet bounds). For any two distinct vertices u , v u,v u , v of a connected graph G G G ,
r u v ≥ 1 d u + 1 d v if u ≁ v , r u v ≥ d u + d v − 2 d u d v − 1 if u ∼ v , r_{uv}\geq\frac{1}{d_u}+\frac{1}{d_v}\qquad\text{if }u\not\sim v,\qquad r_{uv}\geq\frac{d_u+d_v-2}{d_ud_v-1}\qquad\text{if }u\sim v, r uv ≥ d u 1 + d v 1 if u ∼ v , r uv ≥ d u d v − 1 d u + d v − 2 if u ∼ v , and in both cases
r u v ≥ 1 d u + 1 + 1 d v + 1 . r_{uv}\geq\frac{1}{d_u+1}+\frac{1}{d_v+1}. r uv ≥ d u + 1 1 + d v + 1 1 .
Proof. By Thomson’s and Dirichlet’s principles, 1 / r u v 1/r_{uv} 1/ r uv is the minimum of the Dirichlet energy ∑ a b ∈ E ( ψ a − ψ b ) 2 \sum_{ab\in E}(\psi_a-\psi_b)^2 ∑ ab ∈ E ( ψ a − ψ b ) 2 over all functions ψ : V → R \psi:V\to\mathbb{R} ψ : V → R with ψ u = 1 \psi_u=1 ψ u = 1 and ψ v = 0 \psi_v=0 ψ v = 0 . Restricting to test functions that take a constant value c c c on V ∖ { u , v } V\setminus\{u,v\} V ∖ { u , v } gives an upper bound on 1 / r u v 1/r_{uv} 1/ r uv : when u ≁ v u\not\sim v u ∼ v the energy is d u ( 1 − c ) 2 + d v c 2 d_u(1-c)^2+d_vc^2 d u ( 1 − c ) 2 + d v c 2 , which has minimum d u d v / ( d u + d v ) d_ud_v/(d_u+d_v) d u d v / ( d u + d v ) over c ∈ R c\in\mathbb{R} c ∈ R , and when u ∼ v u\sim v u ∼ v the energy is 1 + ( d u − 1 ) ( 1 − c ) 2 + ( d v − 1 ) c 2 1+(d_u-1)(1-c)^2+(d_v-1)c^2 1 + ( d u − 1 ) ( 1 − c ) 2 + ( d v − 1 ) c 2 , which has minimum ( d u d v − 1 ) / ( d u + d v − 2 ) (d_ud_v-1)/(d_u+d_v-2) ( d u d v − 1 ) / ( d u + d v − 2 ) . Taking reciprocals yields the first two inequalities. The unified bound follows because 1 d u + 1 d v > 1 d u + 1 + 1 d v + 1 \frac{1}{d_u}+\frac{1}{d_v}>\frac{1}{d_u+1}+\frac{1}{d_v+1} d u 1 + d v 1 > d u + 1 1 + d v + 1 1 and
d u + d v − 2 d u d v − 1 − ( 1 d u + 1 + 1 d v + 1 ) = ( d u − d v ) 2 ( d u d v − 1 ) ( d u + 1 ) ( d v + 1 ) ≥ 0. \frac{d_u+d_v-2}{d_ud_v-1}-\left(\frac{1}{d_u+1}+\frac{1}{d_v+1}\right)=\frac{(d_u-d_v)^2}{(d_ud_v-1)(d_u+1)(d_v+1)}\geq0. d u d v − 1 d u + d v − 2 − ( d u + 1 1 + d v + 1 1 ) = ( d u d v − 1 ) ( d u + 1 ) ( d v + 1 ) ( d u − d v ) 2 ≥ 0.
What resistance-regularity forces
Before constructing non-regular examples, we establish the spectral and structural constraints stated in Theorem A and use them to rule out small counterexamples by exhaustive enumeration.
Proof of Theorem A
Parts (i) and (ii) of Theorem A concern the moments of the local spectral measure. Write P = I − J / n P=I-J/n P = I − J / n , and for each integer s s s define L ( s ) = L s L^{(s)}=L^s L ( s ) = L s when s ≥ 1 s\ge1 s ≥ 1 , L ( 0 ) = P L^{(0)}=P L ( 0 ) = P , and L ( s ) = ( L † ) − s L^{(s)}=(L^\dagger)^{-s} L ( s ) = ( L † ) − s when s ≤ − 1 s\le-1 s ≤ − 1 , so that L ( s ) = ∑ i = 1 m μ i s E i L^{(s)}=\sum_{i=1}^{m}\mu_i^sE_i L ( s ) = ∑ i = 1 m μ i s E i and ( L ( s ) ) v v = ∑ i = 1 m μ i s e i ( v ) (L^{(s)})_{vv}=\sum_{i=1}^{m}\mu_i^se_i(v) ( L ( s ) ) v v = ∑ i = 1 m μ i s e i ( v ) for all s ∈ Z s\in\mathbb{Z} s ∈ Z . Alongside a Vandermonde inversion argument, the proof relies on linear relations between positive and negative powers of L L L inherited from its minimal polynomial on 1 ⊥ 1^\perp 1 ⊥ .
Lemma 3.1. Let G G G be a connected graph whose Laplacian has the distinct nonzero eigenvalues μ 1 , … , μ m \mu_1,\ldots,\mu_m μ 1 , … , μ m , and let σ 0 = 1 , σ 1 , … , σ m \sigma_0=1,\sigma_1,\ldots,\sigma_m σ 0 = 1 , σ 1 , … , σ m be their elementary symmetric functions. Then for every integer j j j ,
∑ k = 0 m ( − 1 ) k σ k L ( m − k − j ) = 0. \sum_{k=0}^{m}(-1)^k\sigma_kL^{(m-k-j)}=0. k = 0 ∑ m ( − 1 ) k σ k L ( m − k − j ) = 0.
Proof. By the spectral decomposition, the left-hand side equals ∑ i = 1 m c i E i \sum_{i=1}^{m}c_iE_i ∑ i = 1 m c i E i with
c i = ∑ k = 0 m ( − 1 ) k σ k μ i m − k − j = μ i − j ∏ l = 1 m ( μ i − μ l ) = 0. c_i=\sum_{k=0}^{m}(-1)^k\sigma_k\mu_i^{m-k-j}=\mu_i^{-j}\prod_{l=1}^{m}(\mu_i-\mu_l)=0. c i = k = 0 ∑ m ( − 1 ) k σ k μ i m − k − j = μ i − j l = 1 ∏ m ( μ i − μ l ) = 0.
For m = 3 m=3 m = 3 and j = 1 , 2 j=1,2 j = 1 , 2 , Lemma 3.1 gives
L 2 − σ 1 L + σ 2 P − σ 3 L † = 0 , L − σ 1 P + σ 2 L † − σ 3 ( L † ) 2 = 0. (4) L^2-\sigma_1L+\sigma_2P-\sigma_3L^\dagger=0,\qquad L-\sigma_1P+\sigma_2L^\dagger-\sigma_3(L^\dagger)^2=0. \tag*{(4)} L 2 − σ 1 L + σ 2 P − σ 3 L † = 0 , L − σ 1 P + σ 2 L † − σ 3 ( L † ) 2 = 0. (4)
Proof of Theorem A. (i) Fix a vertex v v v . Since ∑ i = 1 m e i ( v ) = 1 − 1 / n \sum_{i=1}^{m}e_i(v)=1-1/n ∑ i = 1 m e i ( v ) = 1 − 1/ n , the weights e i ( v ) e_i(v) e i ( v ) of the local spectral measure at v v v satisfy the linear system
∑ i = 1 m μ i − s e i ( v ) = ( L ( − s ) ) v v , s = 0 , 1 , … , m − 1 , (5) \sum_{i=1}^{m}\mu_i^{-s}e_i(v)=(L^{(-s)})_{vv},\qquad s=0,1,\ldots,m-1, \tag*{(5)} i = 1 ∑ m μ i − s e i ( v ) = ( L ( − s ) ) v v , s = 0 , 1 , … , m − 1 , (5)
as well as the system with μ i s \mu_i^s μ i s and ( L ( s ) ) v v (L^{(s)})_{vv} ( L ( s ) ) v v in place of μ i − s \mu_i^{-s} μ i − s and ( L ( − s ) ) v v (L^{(-s)})_{vv} ( L ( − s ) ) v v . The coefficient matrices of the two systems are the Vandermonde matrices in the distinct numbers μ 1 − 1 , … , μ m − 1 \mu_1^{-1},\ldots,\mu_m^{-1} μ 1 − 1 , … , μ m − 1 and μ 1 , … , μ m \mu_1,\ldots,\mu_m μ 1 , … , μ m ; they are invertible and do not depend on v v v . Hence the local spectral measure at v v v is determined by the diagonal entries of L † , ( L † ) 2 , … , ( L † ) m − 1 L^\dagger,(L^\dagger)^2,\ldots,(L^\dagger)^{m-1} L † , ( L † ) 2 , … , ( L † ) m − 1 at v v v , and also by the diagonal entries of L , L 2 , … , L m − 1 L,L^2,\ldots,L^{m-1} L , L 2 , … , L m − 1 at $v.
Suppose that G G G is walk-regular. Then G G G is regular of some degree d d d , so L = d I − A L=dI-A L = d I − A , and ( L k ) v v (L^k)_{vv} ( L k ) v v is a linear combination of the numbers ( A j ) v v (A^j)_{vv} ( A j ) v v , $0\le j\le k$, with coefficients that depend only on d d d and k k k . Thus no diagonal entry of a power of L L L depends on v v v , so the local spectral measure does not depend on v v v , and neither does ( ( L † ) k ) v v = ∑ i = 1 m μ i − k e i ( v ) ((L^\dagger)^k)_{vv}=\sum_{i=1}^{m}\mu_i^{-k}e_i(v) (( L † ) k ) v v = ∑ i = 1 m μ i − k e i ( v ) for any k ≥ 1 k\ge1 k ≥ 1 . Conversely, suppose that the diagonal entries of L † , ( L † ) 2 , … , ( L † ) m − 1 L^\dagger,(L^\dagger)^2,\ldots,(L^\dagger)^{m-1} L † , ( L † ) 2 , … , ( L † ) m − 1 are all constant. Then the local spectral measure does not depend on v v v , and hence neither does ( L k ) v v = ∑ i = 1 m μ i k e i ( v ) (L^k)_{vv}=\sum_{i=1}^{m}\mu_i^ke_i(v) ( L k ) v v = ∑ i = 1 m μ i k e i ( v ) for any k ≥ 1. T a k i n g k\ge1. Taking k ≥ 1. T ak in g k=1$ shows that G G G is regular, say of degree d d d . Then A = d I − L A=dI-L A = d I − L , so ( A k ) v v (A^k)_{vv} ( A k ) v v is a linear combination of the numbers ( L j ) v v (L^j)_{vv} ( L j ) v v , 0 ≤ j ≤ k 0\le j\le k 0 ≤ j ≤ k , with coefficients that do not depend on v v v , and G G G is walk-regular.
(ii) If m ≤ 2 m\le2 m ≤ 2 , the conditions in (i) consist of the constancy of L v v † L^\dagger_{vv} L v v † alone, or are empty when m = 1 m=1 m = 1 , so a resistance-regular graph with m ≤ 2 m\le2 m ≤ 2 is walk-regular by (i). Now let m = 3 m=3 m = 3 . Since ( L 2 ) v v = d v 2 + d v (L^2)_{vv}=d_v^2+d_v ( L 2 ) v v = d v 2 + d v and P v v = 1 − 1 / n P_{vv}=1-1/n P v v = 1 − 1/ n , the diagonal of the first identity in (4) reads
σ 3 L v v † = d v 2 + ( 1 − σ 1 ) d v + σ 2 ( 1 − 1 n ) . (6) \sigma_3L^\dagger_{vv}=d_v^2+(1-\sigma_1)d_v+\sigma_2\left(1-\frac{1}{n}\right). \tag*{(6)} σ 3 L v v † = d v 2 + ( 1 − σ 1 ) d v + σ 2 ( 1 − n 1 ) . (6)
If L v v † L^\dagger_{vv} L v v † is constant, every degree is therefore a root of one and the same quadratic polynomial z 2 + ( 1 − σ 1 ) z + c z^2+(1-\sigma_1)z+c z 2 + ( 1 − σ 1 ) z + c . Hence there are at most two distinct degrees, and two distinct roots add up to σ 1 − 1 \sigma_1-1 σ 1 − 1 .
(iii) Let G G G be resistance-regular but not regular. By Proposition 2.5 , G G G is 2-connected, so every vertex has degree at least 2. Suppose for a contradiction that some vertex v v v has degree 2, with neighbours a a a and b b b . Since G G G is 2-connected, G ′ = G − v G' = G - v G ′ = G − v is connected on n − 1 n - 1 n − 1 vertices; let r ′ r' r ′ denote the effective resistance between a a a and b b b in G ′ G' G ′ . Because v a va v a and v b vb v b are the only edges incident to v v v , the network between v v v and a a a places the unit resistor v a va v a in parallel with the series combination of v b vb v b and G ′ G' G ′ . Thus r v a = ( 1 + r ′ ) / ( 2 + r ′ ) r_{va} = (1 + r')/(2 + r') r v a = ( 1 + r ′ ) / ( 2 + r ′ ) , and by symmetry r v b = ( 1 + r ′ ) / ( 2 + r ′ ) r_{vb} = (1 + r')/(2 + r') r v b = ( 1 + r ′ ) / ( 2 + r ′ ) as well. Applying Theorem 2.4 (iii) at v v v gives 2 ( 1 + r ′ ) / ( 2 + r ′ ) = 2 − 2 / n 2(1 + r')/(2 + r') = 2 - 2/n 2 ( 1 + r ′ ) / ( 2 + r ′ ) = 2 − 2/ n , which forces r ′ = n − 2 r' = n - 2 r ′ = n − 2 . By Thomson’s principle [6 ] , however, r ′ r' r ′ is the minimum energy of a unit flow from a a a to b b b in G ′ G' G ′ and therefore cannot exceed the length of a shortest a a a –b b b path P ′ P' P ′ in G ′ G' G ′ , which is at most n − 2 n - 2 n − 2 . Equality requires P ′ P' P ′ to have length n − 2 n - 2 n − 2 (visiting all n − 1 n - 1 n − 1 vertices of G ′ G' G ′ ) and the unit flow along P ′ P' P ′ to be the unique electrical current from a a a to b b b in G ′ G' G ′ . Since the potential drops by 1 along each edge of P ′ P' P ′ , any additional edge in G ′ G' G ′ would connect two vertices at different potentials and carry nonzero current. It follows that G ′ = P ′ G' = P' G ′ = P ′ and G G G is the cycle C n C_n C n , contradicting the assumption that G G G is non-regular. Every vertex of G G G must therefore have degree at least 3.
Next, let G ‾ \overline{G} G be the complement of G G G , with Laplacian L ‾ \overline{L} L and degrees h v = n − 1 − d v h_v = n - 1 - d_v h v = n − 1 − d v . Since L = n I − J − L ‾ L = nI - J - \overline{L} L = n I − J − L and L ‾ 1 = 0 \overline{L}\mathbf{1} = 0 L 1 = 0 , the matrix n I − L ‾ nI - \overline{L} n I − L is invertible (its eigenvalue on 1 \mathbf{1} 1 is n n n , and on 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ it agrees with L L L ) and L † = ( n I − L ‾ ) − 1 − J / n 2 L^\dagger= (nI - \overline{L})^{-1} - J/n^2 L † = ( n I − L ) − 1 − J / n 2 . Hence G G G is resistance-regular if and only if f v = [ ( n I − L ‾ ) − 1 ] v v f_v = [(nI - \overline{L})^{-1}]_{vv} f v = [( n I − L ) − 1 ] v v is independent of v v v . Let ν v \nu_v ν v be the local spectral measure of L ‾ \overline{L} L at v v v , now including the eigenvalue 0, so that ν v \nu_v ν v is a probability measure with mean ∫ λ d ν v = h v \int\lambda\,d\nu_v = h_v ∫ λ d ν v = h v and second moment ( L ‾ 2 ) v v = h v 2 + h v (\overline{L}^2)_{vv} = h_v^2 + h_v ( L 2 ) v v = h v 2 + h v , hence variance h v h_v h v . If v v v lies in a component of G ‾ \overline{G} G with c v c_v c v vertices, ν v \nu_v ν v is supported on the Laplacian eigenvalues of that component, which lie in [ 0 , c v ] [0,c_v] [ 0 , c v ] [26 ] . Integrating the identity
1 n − λ = 1 n − h + λ − h ( n − h ) 2 + ( λ − h ) 2 ( n − h ) 2 ( n − λ ) \frac{1}{n-\lambda} = \frac{1}{n-h} + \frac{\lambda-h}{(n-h)^2} + \frac{(\lambda-h)^2}{(n-h)^2(n-\lambda)} n − λ 1 = n − h 1 + ( n − h ) 2 λ − h + ( n − h ) 2 ( n − λ ) ( λ − h ) 2
with h = h v h = h_v h = h v against ν v \nu_v ν v gives f v = 1 n − h v + K v ( n − h v ) 2 f_v = \frac{1}{n-h_v} + \frac{K_v}{(n-h_v)^2} f v = n − h v 1 + ( n − h v ) 2 K v with 0 ≤ K v ≤ h v / ( n − c v ) 0 \leq K_v \leq h_v/(n-c_v) 0 ≤ K v ≤ h v / ( n − c v ) whenever c v < n c_v < n c v < n .
Now suppose that G ‾ \overline{G} G is disconnected and that u u u and w w w lie in different components with d u < d w d_u < d_w d u < d w , that is, h u > h w h_u > h_w h u > h w . Then h w < h u ≤ c u − 1 ≤ n − c w − 1 h_w < h_u \leq c_u - 1 \leq n - c_w - 1 h w < h u ≤ c u − 1 ≤ n − c w − 1 , so K w < 1 K_w < 1 K w < 1 , and
f u − f w ≥ 1 n − h u − 1 n − h w − K w ( n − h w ) 2 = ( h u − h w ) ( n − h w ) − K w ( n − h u ) ( n − h u ) ( n − h w ) 2 > 0 , f_u - f_w \geq\frac{1}{n-h_u} - \frac{1}{n-h_w} - \frac{K_w}{(n-h_w)^2} = \frac{(h_u-h_w)(n-h_w)-K_w(n-h_u)}{(n-h_u)(n-h_w)^2} > 0, f u − f w ≥ n − h u 1 − n − h w 1 − ( n − h w ) 2 K w = ( n − h u ) ( n − h w ) 2 ( h u − h w ) ( n − h w ) − K w ( n − h u ) > 0 ,
because h u − h w ≥ 1 h_u - h_w \geq1 h u − h w ≥ 1 and n − h w > n − h u n - h_w > n - h_u n − h w > n − h u , which contradicts resistance-regularity. Thus, if G ‾ \overline{G} G is disconnected, any two vertices in different components of G ‾ \overline{G} G have the same degree in G G G ; since every vertex has a vertex in another component, all degrees are equal, contrary to our assumption. Hence G ‾ \overline{G} G is connected. In particular, G G G is not the join of two graphs, and no vertex of G G G is adjacent to all other vertices, since such a vertex would be isolated in G ‾ \overline{G} G .
Finally, every edge of a bipartite graph has exactly one end in each colour class U U U . If G G G is bipartite, summing Theorem 2.4 (iii) over v ∈ U v \in U v ∈ U and using Foster’s identity gives ∣ U ∣ ( 2 − 2 / n ) = ∑ u v ∈ E r u v = n − 1 |U|(2 - 2/n) = \sum_{uv\in E} r_{uv} = n - 1 ∣ U ∣ ( 2 − 2/ n ) = ∑ uv ∈ E r uv = n − 1 , so ∣ U ∣ = n / 2 |U| = n/2 ∣ U ∣ = n /2 . □
When m ≥ 3 m \geq3 m ≥ 3 , the two equations s = 0 s = 0 s = 0 and s = 1 s = 1 s = 1 of (5) no longer determine the m m m weights e i ( v ) e_i(v) e i ( v ) , and § 4 shows that the degrees can then indeed differ. For m = 2 m = 2 m = 2 , by contrast, Lemma 3.1 with j = 1 j = 1 j = 1 gives L − σ 1 P + σ 2 L † = 0 L - \sigma_1P + \sigma_2L^\dagger= 0 L − σ 1 P + σ 2 L † = 0 , whose diagonal d v = σ 1 ( 1 − 1 / n ) − σ 2 L v v † d_v = \sigma_1(1 - 1/n) - \sigma_2L^\dagger_{vv} d v = σ 1 ( 1 − 1/ n ) − σ 2 L v v † expresses the degree through L v v † L^\dagger_{vv} L v v † . Zhou, Wang and Bu [17 Theorem 14] derived this identity for a graph with two distinct nonzero Laplacian eigenvalues and then concluded that G G G is regular from the constancy of L v v † L^\dagger_{vv} L v v † ; reading the diagonal of the identity is what makes the conclusion valid. Since constancy of L v v † L^\dagger_{vv} L v v † alone does not imply regularity (Theorem B), a linear relation of this kind between L L L and L † L^\dagger L † , which exists exactly when m = 2 m = 2 m = 2 , is essential to their argument. We record the resulting statement.
Corollary 3.2 ([17 Theorem 14] ). A connected resistance-regular graph whose resistance matrix R R R has exactly three distinct eigenvalues is strongly regular.
Proof. By Theorem 2.4 (iv), the eigenvalues of R R R are 2 Kf ( G ) / n > 0 2\operatorname{Kf}(G)/n > 0 2 Kf ( G ) / n > 0 together with − 2 / μ i < 0 -2/\mu_i < 0 − 2/ μ i < 0 for 1 ≤ i ≤ m 1 \le i \le m 1 ≤ i ≤ m . Thus R R R has exactly three distinct eigenvalues if and only if L L L has m = 2 m=2 m = 2 distinct nonzero eigenvalues. By Theorem A(ii), G G G is regular, and a connected regular graph with three distinct eigenvalues is strongly regular [27 Lemma 10.2.1] .
The second identity in (4) also controls the next negative moment when m = 3 m=3 m = 3 ; we shall use this in § 7.1 .
Corollary 3.3. Let G G G be a connected resistance-regular graph whose Laplacian has exactly three distinct nonzero eigenvalues. Then ( L † ) v v 2 (L^\dagger)^2_{vv} ( L † ) v v 2 is a strictly increasing function of d v d_v d v .
Proof. The diagonal of the second identity in (4) reads σ 3 ( L † ) v v 2 = d v − σ 1 ( 1 − 1 / n ) + σ 2 L v v † \sigma_3 (L^\dagger)^2_{vv}=d_v-\sigma_1(1-1/n)+\sigma_2L^\dagger_{vv} σ 3 ( L † ) v v 2 = d v − σ 1 ( 1 − 1/ n ) + σ 2 L v v † . Since L v v † L^\dagger_{vv} L v v † is constant and σ 3 > 0 \sigma_3>0 σ 3 > 0 , the claim follows.
Small graphs
Theorem A(iii) and Proposition 2.5 make an exhaustive search of small graphs feasible: a non-regular resistance-regular graph is 2-connected and has minimum degree at least 3. We enumerated graphs with geng from the nauty package [28 ] and used two tests (Table 1). For n ≤ 10 n \le10 n ≤ 10 we tested all connected graphs in exact integer arithmetic: fraction-free Gaussian elimination of the Laplacian with one row and column removed gives the number τ \tau τ of spanning trees and the integers τ r u v \tau r_{uv} τ r uv , and a graph is resistance-regular exactly when the integer row sums ∑ u τ r u v \sum_u \tau r_{uv} ∑ u τ r uv are equal.
For 11 ≤ n ≤ 13 11 \le n \le13 11 ≤ n ≤ 13 we restricted the enumeration to 2-connected graphs with minimum degree at least 3 and compiled a two-stage floating-point filter directly into geng so that graphs could be screened on the fly without disk storage. In the first stage, the diagonal entries of ( L + J / n ) − 1 (L+J/n)^{-1} ( L + J / n ) − 1 at one vertex of maximum degree and one of minimum degree are estimated in single precision by eliminating the other n − 2 n-2 n − 2 vertices, discarding the graph only if those two entries differ by more than 10%. For every graph that survives this coarse check, the second stage computes the full diagonal of ( L + J / n ) − 1 (L+J/n)^{-1} ( L + J / n ) − 1 in double precision via Cholesky factorisation and flags the graph as a candidate whenever the relative spread ( max − min ) / min (\max-\min)/\min ( max − min ) / min falls below 10 − 7 10^{-7} 1 0 − 7 . Both stages rely solely on pivot-free symmetric elimination of the positive definite matrix L + J / n L+J/n L + J / n , whose eigenvalues lie in [ λ , n ] [\lambda,n] [ λ , n ] with λ ≥ min { 1 , 4 ( 1 − cos ( π / n ) ) } \lambda\ge\min\{1,4(1-\cos(\pi/n))\} λ ≥ min { 1 , 4 ( 1 − cos ( π / n ))} for 2-connected graphs [29 ] . Standard backward-error analysis [30 ] guarantees that for n ≤ 13 n \le13 n ≤ 13 the relative error in every computed diagonal entry is below 4 × 10 − 3 4\times10^{-3} 4 × 1 0 − 3 in the first stage and below 10 − 10 10^{-10} 1 0 − 10 in the second (see the ancillary documentation for details), leaving a wide safety margin below both thresholds. As an empirical validation, the compiled filter correctly identified random relabellings of all 23 known non-regular resistance-regular graphs on at most 32 vertices, and in the regular degree classes tested on 12 and 13 vertices (degrees 3, 4, 5 for n = 12 n=12 n = 12 and degrees 4, 6 for n = 13 n=13 n = 13 ) it accepted the exact set of resistance-regular graphs determined by rational arithmetic.
For n = 12 n=12 n = 12 this covers all 113 372 069 299 two-connected graphs of minimum degree at least 3, of which 18 972 are regular. No candidate appeared; the smallest relative spread among the non-regular graphs is 4 / 125 4/125 4/125 , attained by a graph with six vertices of degree 4 and six of degree 5. For n = 13 n=13 n = 13 , where there are about 5 × 10 13 5\times10^{13} 5 × 1 0 13 connected graphs, we covered all 2-connected graphs of minimum degree at least 3 whose degrees lie in a window { k , k + 1 , k + 2 } \{k,k+1,k+2\} { k , k + 1 , k + 2 } for k = 3 , … , 7 k=3,\ldots,7 k = 3 , … , 7 , and all graphs of minimum degree at least 8. These runs include every graph on 13 vertices whose maximum and minimum degree differ by at most 2 and that is not excluded by Proposition 2.5 and Theorem A(iii). The runs were split into residue classes of geng, and the coverage and the totals in Table 1 can be checked from the per-chunk records in the ancillary files. As an independent check, a double-precision screen of all connected graphs of minimum degree at least 2 on at most 10 vertices and of all 900 969 091 two-connected graphs on 11 vertices (a number that agrees with sequence A002218 in [31 ] ), with exact verification of every graph passing the screen, found no non-regular resistance-regular graph either.
Table 1. Exhaustive enumerations of small graphs with geng; δ \delta δ denotes the minimum degree; exact refers to the test in exact integer arithmetic and built-in to the floating-point test built into geng, both described in the text. Every resistance-regular graph in these classes is regular. For n = 13 n=13 n = 13 the counts are summed over the degree windows, so graphs whose degrees lie in two windows are counted twice.
Proposition 3.4 (computer-assisted). Every resistance-regular graph on at most 12 vertices is regular. Every resistance-regular graph on 13 vertices whose maximum and minimum degree differ by at most 2, or whose minimum degree is at least 8, is regular.
Proof. No non-regular resistance-regular graph was found in any of the enumerations summarised in Table 1. By Proposition 2.5 and Theorem A(iii), any graph on 11 or 12 vertices omitted from the search, as well as any 13-vertex graph satisfying the stated degree conditions but omitted from the search, cannot be a non-regular resistance-regular graph.
Consequently, the minimum order of a non-regular resistance-regular graph is at least 13; the graph F ( 4 ) \mathcal{F}(4) F ( 4 ) constructed in the next section shows that it is at most 16.
Existence: a family of non-regular resistance-regular graphs
By Proposition 3.4, a non-regular resistance-regular graph has at least 13 vertices, and by Theorem A(ii) its Laplacian has at least three distinct nonzero eigenvalues. Since an exhaustive search becomes infeasible beyond 13 vertices, we turned to graphs with a large group of automorphisms, for which the diagonal of L † L^{\dagger} L † can be computed from small matrices. In this section we describe this search and the infinite family that it revealed, and we prove Theorem B.
Bi-Cayley graphs and a computer search
We consider graphs that have a semiregular group of automorphisms with two orbits; these are the bi-Cayley graphs, whose automorphisms were studied by Zhou and Feng [32 ] .
Definition 4.1 (bi-Cayley graph). Let H H H be a finite abelian group, written additively, with character group H ^ \widehat{H} H . Given inverse-closed subsets S 11 , S 22 ⊆ H ∖ { 0 } S_{11},S_{22} \subseteq H \setminus\{0\} S 11 , S 22 ⊆ H ∖ { 0 } and an arbitrary subset S 12 ⊆ H S_{12} \subseteq H S 12 ⊆ H , the bi-Cayley graph BiCay ( H ; S 11 , S 22 , S 12 ) \operatorname{BiCay}(H;S_{11},S_{22},S_{12}) BiCay ( H ; S 11 , S 22 , S 12 ) has vertex set H × { 1 , 2 } H \times\{1,2\} H × { 1 , 2 } and edges
( h , 1 ) ∼ ( h + s , 1 ) ( s ∈ S 11 ) , ( h , 2 ) ∼ ( h + s , 2 ) ( s ∈ S 22 ) , ( h , 1 ) ∼ ( h + s , 2 ) ( s ∈ S 12 ) . (h,1) \sim(h+s,1)\ (s \in S_{11}), \qquad(h,2) \sim(h+s,2)\ (s \in S_{22}), \qquad(h,1) \sim(h+s,2)\ (s \in S_{12}). ( h , 1 ) ∼ ( h + s , 1 ) ( s ∈ S 11 ) , ( h , 2 ) ∼ ( h + s , 2 ) ( s ∈ S 22 ) , ( h , 1 ) ∼ ( h + s , 2 ) ( s ∈ S 12 ) .
Left translation by H H H acts semiregularly on the vertices with the two orbits H × { 1 } H \times\{1\} H × { 1 } and H × { 2 } H \times\{2\} H × { 2 } , which have constant degrees d 1 = ∣ S 11 ∣ + ∣ S 12 ∣ d_1 = |S_{11}| + |S_{12}| d 1 = ∣ S 11 ∣ + ∣ S 12 ∣ and d 2 = ∣ S 22 ∣ + ∣ S 12 ∣ d_2 = |S_{22}| + |S_{12}| d 2 = ∣ S 22 ∣ + ∣ S 12 ∣ . For a character χ ∈ H ^ \chi\in\widehat{H} χ ∈ H and a subset S ⊆ H S \subseteq H S ⊆ H , write χ ( S ) = ∑ s ∈ S χ ( s ) \chi(S) = \sum_{s \in S}\chi(s) χ ( S ) = ∑ s ∈ S χ ( s ) ; when S = − S S=-S S = − S , χ ( S ) \chi(S) χ ( S ) is real. Because the four orbit blocks of L L L lie in the group algebra of H H H , the characters of H H H simultaneously block-diagonalise L L L . Specifically, L L L is unitarily similar to the direct sum over χ ∈ H ^ \chi\in\widehat{H} χ ∈ H of the 2 × 2 2 \times2 2 × 2 Hermitian matrices
L ^ χ = ( d 1 − χ ( S 11 ) − χ ( S 12 ) − χ ( S 12 ) ‾ d 2 − χ ( S 22 ) ) (7) \widehat{L}_{\chi} =
\begin{pmatrix}
d_1-\chi(S_{11}) & -\chi(S_{12}) \\
-\overline{\chi(S_{12})} & d_2-\chi(S_{22})
\end{pmatrix} \tag*{(7)} L χ = ( d 1 − χ ( S 11 ) − χ ( S 12 ) − χ ( S 12 ) d 2 − χ ( S 22 ) ) (7)
(see [33 ] ). Inverting these 2 × 2 2 \times2 2 × 2 blocks gives an explicit criterion for resistance-regularity.
Lemma 4.2. Let G = BiCay ( H ; S 11 , S 22 , S 12 ) G = \operatorname{BiCay}(H; S_{11}, S_{22}, S_{12}) G = BiCay ( H ; S 11 , S 22 , S 12 ) with H H H abelian and S 12 ≠ ∅ S_{12} \ne\varnothing S 12 = ∅ . Then G G G is connected if and only if det L ^ χ ≠ 0 \det\widehat{L}_{\chi} \ne0 det L χ = 0 for every nontrivial character χ ∈ H ^ ∖ { 1 } \chi\in\widehat{H} \setminus\{1\} χ ∈ H ∖ { 1 } . In that case, for every h ∈ H h \in H h ∈ H ,
L ( h , 1 ) , ( h , 1 ) † = 1 4 ∣ H ∣ ∣ S 12 ∣ + 1 ∣ H ∣ ∑ χ ≠ 1 d 2 − χ ( S 22 ) det L ^ χ , (8) L^{\dagger}_{(h,1),(h,1)} = \frac{1}{4|H||S_{12}|} + \frac{1}{|H|}\sum_{\chi\ne1}\frac{d_2-\chi(S_{22})}{\det\widehat{L}_{\chi}}, \tag*{(8)} L ( h , 1 ) , ( h , 1 ) † = 4∣ H ∣∣ S 12 ∣ 1 + ∣ H ∣ 1 χ = 1 ∑ det L χ d 2 − χ ( S 22 ) , (8) L ( h , 2 ) , ( h , 2 ) † = 1 4 ∣ H ∣ ∣ S 12 ∣ + 1 ∣ H ∣ ∑ χ ≠ 1 d 1 − χ ( S 11 ) det L ^ χ . (9) L^{\dagger}_{(h,2),(h,2)} = \frac{1}{4|H||S_{12}|} + \frac{1}{|H|}\sum_{\chi\ne1}\frac{d_1-\chi(S_{11})}{\det\widehat{L}_{\chi}}. \tag*{(9)} L ( h , 2 ) , ( h , 2 ) † = 4∣ H ∣∣ S 12 ∣ 1 + ∣ H ∣ 1 χ = 1 ∑ det L χ d 1 − χ ( S 11 ) . (9) In particular, G G G is resistance-regular if and only if
∑ χ ≠ 1 ( d 2 − χ ( S 22 ) ) − ( d 1 − χ ( S 11 ) ) det L ^ χ = 0. (10) \sum_{\chi\ne1}\frac{(d_2-\chi(S_{22}))-(d_1-\chi(S_{11}))}{\det\widehat{L}_{\chi}}=0. \tag*{(10)} χ = 1 ∑ det L χ ( d 2 − χ ( S 22 )) − ( d 1 − χ ( S 11 )) = 0. (10)
Proof. Let U U U be the unitary character table of H H H with columns ∣ H ∣ − 1 / 2 χ |H|^{-1/2}\chi ∣ H ∣ − 1/2 χ for χ ∈ H ^ \chi\in\widehat{H} χ ∈ H . Conjugating L L L by U ⊕ U U \oplus U U ⊕ U and reordering coordinates block-diagonalises L L L into ⨁ χ ∈ H ^ L ^ χ \bigoplus_{\chi\in\widehat{H}}\widehat{L}_{\chi} ⨁ χ ∈ H L χ , so dim ker L = ∑ χ dim ker L ^ χ \dim\ker L = \sum_{\chi}\dim\ker\widehat{L}_{\chi} dim ker L = ∑ χ dim ker L χ . For the trivial character χ = 1 \chi=1 χ = 1 , we have χ ( S i i ) = ∣ S i i ∣ \chi(S_{ii})=|S_{ii}| χ ( S ii ) = ∣ S ii ∣ and χ ( S 12 ) = ∣ S 12 ∣ \chi(S_{12})=|S_{12}| χ ( S 12 ) = ∣ S 12 ∣ , so L ^ 1 = ∣ S 12 ∣ ( 1 − 1 − 1 1 ) \widehat{L}_{1}=|S_{12}|\begin{pmatrix}1 & -1\\-1 & 1\end{pmatrix} L 1 = ∣ S 12 ∣ ( 1 − 1 − 1 1 ) , which has a one-dimensional kernel because S 12 ≠ ∅ S_{12}\ne\varnothing S 12 = ∅ . Thus ker L \ker L ker L is one-dimensional, meaning that G G G is connected, if and only if det L ^ χ ≠ 0 \det\widehat{L}_{\chi}\ne0 det L χ = 0 for all χ ≠ 1 \chi\ne1 χ = 1 .
Since the Moore–Penrose inverse respects unitary similarity and direct sums, L † = ( U ⊕ U ) ( ⨁ χ L ^ χ † ) ( U ⊕ U ) ∗ L^{\dagger}=(U\oplus U)\left(\bigoplus_{\chi}\widehat{L}_{\chi}^{\dagger}\right)(U\oplus U)^* L † = ( U ⊕ U ) ( ⨁ χ L χ † ) ( U ⊕ U ) ∗ . Because every entry of U U U has modulus ∣ H ∣ − 1 / 2 |H|^{-1/2} ∣ H ∣ − 1/2 , the diagonal entry of L † L^{\dagger} L † at ( h , i ) (h,i) ( h , i ) is simply the average of the ( i , i ) (i,i) ( i , i ) entries of L ^ χ † \widehat{L}_{\chi}^{\dagger} L χ † over all χ ∈ H ^ \chi\in\widehat{H} χ ∈ H . For χ = 1 \chi=1 χ = 1 , L ^ 1 † = ( 4 ∣ S 12 ∣ ) − 1 ( 1 − 1 − 1 1 ) \widehat{L}_{1}^{\dagger}=(4|S_{12}|)^{-1}\begin{pmatrix}1 & -1\\-1 & 1\end{pmatrix} L 1 † = ( 4∣ S 12 ∣ ) − 1 ( 1 − 1 − 1 1 ) , which contributes ( 4 ∣ H ∣ ∣ S 12 ∣ ) − 1 (4|H||S_{12}|)^{-1} ( 4∣ H ∣∣ S 12 ∣ ) − 1 to both (8) and (9) . For χ ≠ 1 \chi\ne1 χ = 1 , L ^ χ \widehat{L}_{\chi} L χ is invertible and Cramer’s rule gives ( L ^ χ − 1 ) 11 = ( d 2 − χ ( S 22 ) ) / det L ^ χ (\widehat{L}_{\chi}^{-1})_{11}=(d_2-\chi(S_{22}))/\det\widehat{L}_{\chi} ( L χ − 1 ) 11 = ( d 2 − χ ( S 22 )) / det L χ and ( L ^ χ − 1 ) 22 = ( d 1 − χ ( S 11 ) ) / det L ^ χ (\widehat{L}_{\chi}^{-1})_{22}=(d_1-\chi(S_{11}))/\det\widehat{L}_{\chi} ( L χ − 1 ) 22 = ( d 1 − χ ( S 11 )) / det L χ . This establishes (8) and (9) . Since H H H acts transitively on each of the two orbits, L † L^{\dagger} L † has constant diagonal if and only if (8) and (9) are equal, which is (10) . □
An analogous decomposition holds for non-abelian groups H H H , with characters replaced by irreducible unitary representations ρ \rho ρ and the 2 × 2 2 \times2 2 × 2 blocks (7) replaced by blocks of size 2 dim ρ 2\dim\rho 2 dim ρ ; we used this general form in the search described next.
Lemma 4.2 allows us to test a bi-Cayley graph for resistance-regularity by evaluating 2 × 2 2 \times2 2 × 2 determinants rather than inverting an n × n n \times n n × n matrix. For each finite group H H H , we enumerated triples ( S 11 , S 22 , S 12 ) (S_{11}, S_{22}, S_{12}) ( S 11 , S 22 , S 12 ) of subsets of H H H such that S 11 , S 22 ⊆ H ∖ { e } S_{11},S_{22}\subseteq H\setminus\{e\} S 11 , S 22 ⊆ H ∖ { e } are inverse-closed with ∣ S 11 ∣ < ∣ S 22 ∣ |S_{11}|<|S_{22}| ∣ S 11 ∣ < ∣ S 22 ∣ and e ∈ S 12 e\in S_{12} e ∈ S 12 (both normalisations are without loss of generality up to isomorphism). Keeping the connected graphs with d 1 ≠ d 2 d_1\ne d_2 d 1 = d 2 , we screened each candidate via (10) , or its representation-theoretic analogue for non-abelian H H H , in double precision and verified every surviving graph in exact rational arithmetic. When H H H is abelian, the left-hand side of (10) depends on S 12 S_{12} S 12 only through the squared modulus ∣ χ ( S 12 ) ∣ 2 |\chi(S_{12})|^2 ∣ χ ( S 12 ) ∣ 2 , which makes it possible to batch all subsets S 12 S_{12} S 12 sharing the same Fourier profile. Using this reduction, we searched exhaustively over all groups of order at most 12, all cyclic groups Z k \mathbb{Z}_k Z k with k ≤ 20 k\le20 k ≤ 20 , and the order-16 abelian groups Z 16 \mathbb{Z}_{16} Z 16 , Z 2 × Z 8 \mathbb{Z}_2\times\mathbb{Z}_8 Z 2 × Z 8 , Z 4 × Z 4 \mathbb{Z}_4\times\mathbb{Z}_4 Z 4 × Z 4 and Z 2 2 × Z 4 \mathbb{Z}_2^2\times\mathbb{Z}_4 Z 2 2 × Z 4 (364456403828 connected labelled triples in total. before Fourier grouping), and we also sampled the dihedral groups D 7 , … , D 10 D_7,\ldots,D_{10} D 7 , … , D 10 . Passing graphs were canonicalised up to isomorphism using nauty [28 ] .
The search produced the sixteen pairwise non-isomorphic graphs of Table 2 , each with two consecutive degrees carried by the two orbits of H H H . Over the groups of order at most 8, graph 1, on 16 vertices, is the only example. Graphs 1, 4 and 13 belong to the family of § 4.2 , graph 12 is obtained from graph 1 by a construction of § 5 , and we regard the other twelve as sporadic, although some of them are blow-ups in the sense of that section. Graphs 7, 8 and 9 are cospectral but pairwise non-isomorphic, as are graphs 14 and 15. Graph 3 is a bi-circulant over Z 12 \mathbb{Z}_{12} Z 12 : its first orbit induces the square of the 12-cycle, its second orbit two disjoint copies of K 6 K_6 K 6 on the even and the odd residues, and vertex i i i of the first orbit is joined to the vertices i i i and i + 6 i+6 i + 6 of the second. Graph 16 has an analogous structure over Z 24 \mathbb{Z}_{24} Z 24 , but the same pattern gives no further examples over Z k \mathbb{Z}_k Z k for k ≤ 40 k \le40 k ≤ 40 .
Table 2. The sixteen non-regular resistance-regular graphs found in the bi-Cayley search, ordered by n n n and ∣ E ∣ |E| ∣ E ∣ ; m m m is the number of distinct nonzero Laplacian eigenvalues. Graphs 1, 4 and 13 are F ( 4 ) \mathcal{F}(4) F ( 4 ) , F ( 6 ) \mathcal{F}(6) F ( 6 ) and F ( 8 ) \mathcal{F}(8) F ( 8 ) . Connection sets, and the groups over which each graph arises, are given in Appendix § 10 .
The family F ( p ) \mathcal{F}(p) F ( p )
Graph 1 of Table 2 has 16 vertices of degrees 6 and 7. Inspecting its structure shows that its 16 vertices partition into two 4-cliques Q 0 , Q 1 Q_0,Q_1 Q 0 , Q 1 of degree 7 and two outer sets X 0 , X 1 X_0,X_1 X 0 , X 1 of degree 6: each clique Q b Q_b Q b is completely joined to X b X_b X b , while the eight vertices of X 0 ∪ X 1 X_0 \cup X_1 X 0 ∪ X 1 partition into two induced 4-cycles that weave between the two blocks. Viewing a 4-cycle as the cocktail-party graph K 4 K_4 K 4 minus a perfect matching suggests replacing K 4 K_4 K 4 by K p K_p K p for any even integer p ≥ 4 p \ge4 p ≥ 4 . As we now verify, this generalisation preserves the exact cancellation between the two vertex orbits for every even p ≥ 4 p \ge4 p ≥ 4 .
In the rest of this section, p ≥ 4 p \ge4 p ≥ 4 is an even integer and h = p / 2 h=p/2 h = p /2 .
Definition 4.3. The graph F ( p ) \mathcal{F}(p) F ( p ) has vertex set Q 0 ∪ Q 1 ∪ X 0 ∪ X 1 Q_0 \cup Q_1 \cup X_0 \cup X_1 Q 0 ∪ Q 1 ∪ X 0 ∪ X 1 , where Q 0 Q_0 Q 0 and Q 1 Q_1 Q 1 are disjoint sets of size p p p and X b = { x b , c , t : c ∈ { 0 , 1 } , t ∈ Z h } X_b=\{x_{b,c,t}:c \in\{0,1\},t \in\mathbb{Z}_h\} X b = { x b , c , t : c ∈ { 0 , 1 } , t ∈ Z h } for b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } . Its edges are of three types:
(E1) every pair of distinct vertices inside Q 0 Q_0 Q 0 and every pair inside Q 1 Q_1 Q 1 ;
(E2) every pair { q , x } \{q,x\} { q , x } with q ∈ Q b q \in Q_b q ∈ Q b and x ∈ X b x \in X_b x ∈ X b , for b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } ;
(E3) for each c ∈ { 0 , 1 } c \in\{0,1\} c ∈ { 0 , 1 } , every pair of distinct vertices in Y c = { x b , c , t : b ∈ { 0 , 1 } , t ∈ Z h } Y_c=\{x_{b,c,t}:b \in\{0,1\},t \in\mathbb{Z}_h\} Y c = { x b , c , t : b ∈ { 0 , 1 } , t ∈ Z h } except the h h h matching pairs { x 0 , c , t , x 1 , c , t } \{x_{0,c,t},x_{1,c,t}\} { x 0 , c , t , x 1 , c , t } (t ∈ Z h t \in\mathbb{Z}_h t ∈ Z h ).
As illustrated in Figure 1 , F ( p ) \mathcal{F}(p) F ( p ) consists of two symmetric blocks indexed by b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } . Block b b b contains an internal clique Q b ≅ K p Q_b \cong K_p Q b ≅ K p joined completely to p p p outer vertices X b X_b X b . Across the two blocks, the 2 p 2p 2 p outer vertices split into two sets Y 0 Y_0 Y 0 and Y 1 Y_1 Y 1 of size p p p , each taking h h h vertices from X 0 X_0 X 0 and h h h from X 1 X_1 X 1 . Each Y c Y_c Y c induces a cocktail-party graph (K p K_p K p minus a perfect matching) in which every missing edge pairs a vertex of X 0 X_0 X 0 with the corresponding vertex of X 1 X_1 X 1 . Every vertex in Q b Q_b Q b has p − 1 p-1 p − 1 neighbours in Q b Q_b Q b and p p p in X b X_b X b , giving degree 2 p − 1 2p-1 2 p − 1 ; every vertex in X b X_b X b has p p p neighbours in Q b Q_b Q b and p − 2 p-2 p − 2 in its Y c Y_c Y c , giving degree 2 p − 2 2p-2 2 p − 2 . Thus F ( p ) \mathcal{F}(p) F ( p ) is a non-regular graph on n = 4 p n=4p n = 4 p vertices with p ( 4 p − 3 ) p(4p-3) p ( 4 p − 3 ) edges.
Figure 1. The structure of F ( p ) \mathcal{F}(p) F ( p ) . Double lines indicate complete joins. Inside Y c Y_c Y c every two vertices are adjacent except for the h h h pairs that lie in different blocks and share the same index t t t .
We first realise F ( p ) \mathcal{F}(p) F ( p ) as a bi-Cayley graph and evaluate the character sums that enter Lemma 4.2 .
Lemma 4.4. Let p ≥ 4 p \ge4 p ≥ 4 be even, h = p / 2 h=p/2 h = p /2 , and H = Z 2 × Z 2 × Z h H=\mathbb{Z}_2 \times\mathbb{Z}_2 \times\mathbb{Z}_h H = Z 2 × Z 2 × Z h , with elements written as triples ( c , b , t ) (c,b,t) ( c , b , t ) . Let K = Z 2 × { 0 } × Z h K=\mathbb{Z}_2 \times\{0\} \times\mathbb{Z}_h K = Z 2 × { 0 } × Z h be the index-2 subgroup of elements with b = 0 b=0 b = 0 , and put
S 12 = K , S 22 = K ∖ { 0 } , S 11 = { ( 0 , b , t ) ∈ H : ( b , t ) ∉ { ( 0 , 0 ) , ( 1 , 0 ) } } . S_{12}=K,\qquad S_{22}=K\setminus\{0\},\qquad S_{11}=\{(0,b,t)\in H:(b,t)\notin\{(0,0),(1,0)\}\}. S 12 = K , S 22 = K ∖ { 0 } , S 11 = {( 0 , b , t ) ∈ H : ( b , t ) ∈ / {( 0 , 0 ) , ( 1 , 0 )}} . Then F ( p ) ≅ BiCay ( H ; S 11 , S 22 , S 12 ) \mathcal{F}(p)\cong\operatorname{BiCay}(H;S_{11},S_{22},S_{12}) F ( p ) ≅ BiCay ( H ; S 11 , S 22 , S 12 ) , with the first orbit corresponding to X 0 ∪ X 1 X_0\cup X_1 X 0 ∪ X 1 and the second to Q 0 ∪ Q 1 Q_0\cup Q_1 Q 0 ∪ Q 1 , so that d 1 = 2 p − 2 d_1=2p-2 d 1 = 2 p − 2 and d 2 = 2 p − 1 d_2=2p-1 d 2 = 2 p − 1 . With M 11 = d 1 − χ ( S 11 ) M_{11}=d_1-\chi(S_{11}) M 11 = d 1 − χ ( S 11 ) , M 22 = d 2 − χ ( S 22 ) M_{22}=d_2-\chi(S_{22}) M 22 = d 2 − χ ( S 22 ) and Θ = det L χ = M 11 M 22 − ∣ χ ( S 12 ) ∣ 2 \Theta=\det L_\chi=M_{11}M_{22}-\lvert\chi(S_{12})\rvert^2 Θ = det L χ = M 11 M 22 − ∣ χ ( S 12 ) ∣ 2 , the 2 p − 1 2p-1 2 p − 1 nontrivial characters χ \chi χ of H H H fall into the following five classes:
Table 1 (PDF p. 12).
Here χ α , γ , k ( c , b , t ) = ( − 1 ) α c ( − 1 ) γ b ω k t \chi_{\alpha,\gamma,k}(c,b,t)=(-1)^{\alpha c}(-1)^{\gamma b}\omega^{kt} χ α , γ , k ( c , b , t ) = ( − 1 ) α c ( − 1 ) γ b ω k t for α , γ ∈ Z 2 \alpha,\gamma\in\mathbb{Z}_2 α , γ ∈ Z 2 and k ∈ Z h k\in\mathbb{Z}_h k ∈ Z h , where ω = e 2 π i / h \omega=e^{2\pi i/h} ω = e 2 π i / h .
Proof. Both S 11 S_{11} S 11 and S 22 S_{22} S 22 are closed under negation and exclude 0 0 0 . Identify the first orbit H × { 1 } H\times\{1\} H × { 1 } with X 0 ∪ X 1 X_0\cup X_1 X 0 ∪ X 1 by sending ( ( c , b , t ) , 1 ) ((c,b,t),1) (( c , b , t ) , 1 ) to x b , c , t x_{b,c,t} x b , c , t , and identify the second orbit H × { 2 } H\times\{2\} H × { 2 } with Q 0 ∪ Q 1 Q_0\cup Q_1 Q 0 ∪ Q 1 by using ( c , t ) ∈ Z 2 × Z h (c,t)\in\mathbb{Z}_2\times\mathbb{Z}_h ( c , t ) ∈ Z 2 × Z h to index the p p p vertices of Q b Q_b Q b . Under this identification:
A vertex ( ( c , b , t ) , 1 ) ((c,b,t),1) (( c , b , t ) , 1 ) is adjacent to ( ( c , b , t ) + k , 2 ) ((c,b,t)+k,2) (( c , b , t ) + k , 2 ) for all k ∈ S 12 = K k\in S_{12}=K k ∈ S 12 = K , which ranges over all p p p vertices of Q b Q_b Q b ; this gives the complete joins in (E2).
Two vertices in H × { 1 } H\times\{1\} H × { 1 } are adjacent if and only if their difference lies in S 11 S_{11} S 11 , meaning they share the same c c c coordinate and are neither equal nor a matching pair { x 0 , c , t , x 1 , c , t } \{x_{0,c,t},x_{1,c,t}\} { x 0 , c , t , x 1 , c , t } ; this gives the cocktail-party subgraphs Y 0 Y_0 Y 0 and Y 1 Y_1 Y 1 in (E3).
Hence F ( p ) ≅ BiCay ( H ; S 11 , S 22 , S 12 ) \mathcal{F}(p)\cong\operatorname{BiCay}(H;S_{11},S_{22},S_{12}) F ( p ) ≅ BiCay ( H ; S 11 , S 22 , S 12 ) with orbit degrees d 1 = ∣ S 11 ∣ + ∣ S 12 ∣ = ( p − 2 ) + p = 2 p − 2 d_1=|S_{11}|+|S_{12}|=(p-2)+p=2p-2 d 1 = ∣ S 11 ∣ + ∣ S 12 ∣ = ( p − 2 ) + p = 2 p − 2 and d 2 = ∣ S 22 ∣ + ∣ S 12 ∣ = ( p − 1 ) + p = 2 p − 1 d_2=|S_{22}|+|S_{12}|=(p-1)+p=2p-1 d 2 = ∣ S 22 ∣ + ∣ S 12 ∣ = ( p − 1 ) + p = 2 p − 1 . The characters of H H H are the maps χ α , γ , k \chi_{\alpha,\gamma,k} χ α , γ , k , and summing χ = χ α , γ , k \chi=\chi_{\alpha,\gamma,k} χ = χ α , γ , k over each connection set gives
χ ( S 12 ) = p [ α = 0 , k = 0 ] , χ ( S 22 ) = χ ( S 12 ) − 1 , χ ( S 11 ) = p [ γ = 0 , k = 0 ] − 1 − ( − 1 ) γ , \chi(S_{12})=p[\alpha=0,k=0],\qquad\chi(S_{22})=\chi(S_{12})-1,\qquad\chi(S_{11})=p[\gamma=0,k=0]-1-(-1)^\gamma, χ ( S 12 ) = p [ α = 0 , k = 0 ] , χ ( S 22 ) = χ ( S 12 ) − 1 , χ ( S 11 ) = p [ γ = 0 , k = 0 ] − 1 − ( − 1 ) γ ,
where [ ⋅ ] [\cdot] [ ⋅ ] denotes the Iverson bracket. Evaluating M 11 M_{11} M 11 , M 22 M_{22} M 22 and Θ \Theta Θ for the nontrivial characters gives the table.
The character sums of Lemma 4.4 lead quickly to L v v † L^\dagger_{vv} L v v † , as the proof of Theorem B below shows, but solving the potential equations directly by symmetry gives every entry of L † L^\dagger L † and shows why the edge resistances at the two vertex orbits balance. For a fixed vertex v v v , the column φ = L † e v \varphi=L^\dagger e_v φ = L † e v is the unique vector satisfying L φ = e v − 1 / n L\varphi=e_v-\mathbf{1}/n L φ = e v − 1 / n and 1 T φ = 0 \mathbf{1}^{\mathsf T}\varphi=0 1 T φ = 0 ; physically, φ \varphi φ is the vertex potential when one unit of current enters at v v v and 1 / n 1/n 1/ n leaves at every vertex. Because any automorphism of F ( p ) \mathcal{F}(p) F ( p ) fixing v v v preserves φ \varphi φ , the vector φ \varphi φ is constant on each orbit of the stabiliser of v v v in Aut ( F ( p ) ) \operatorname{Aut}(\mathcal{F}(p)) Aut ( F ( p )) .
Since the vertices of Q 0 Q_0 Q 0 are true twins (having identical closed neighbourhoods), every permutation of Q 0 Q_0 Q 0 or of Q 1 Q_1 Q 1 is an automorphism of F ( p ) \mathcal{F}(p) F ( p ) , as are the translations from H H H . Consequently, the stabiliser of a clique vertex q ∈ Q 0 q\in Q_0 q ∈ Q 0 partitions V V V into five orbits, and the stabiliser of an outer vertex x = x 0 , c , t ∈ X 0 x=x_{0,c,t}\in X_0 x = x 0 , c , t ∈ X 0 partitions V V V into eight orbits.
Lemma 4.5. Let p ≥ 4 p\ge4 p ≥ 4 be even, h = p / 2 h=p/2 h = p /2 and D = 8 p 2 ( p − 2 ) D=8p^2(p-2) D = 8 p 2 ( p − 2 ) . For a clique vertex q ∈ Q 0 q\in Q_0 q ∈ Q 0 and an outer vertex x = x 0 , c , t ∈ X 0 ∩ Y c x=x_{0,c,t}\in X_0\cap Y_c x = x 0 , c , t ∈ X 0 ∩ Y c , the entries of L † e q L^\dagger e_q L † e q and L † e x L^\dagger e_x L † e x on the orbits of the stabilisers of q q q and of x x x , and the resulting effective resistances, are as follows (E E E : edge, N N N : non-edge):
Table 4.5.
Table 4.5.
In particular, L q q † = L x x † = ( 4 p 2 − 3 p − 2 ) / D L^\dagger_{qq}=L^\dagger_{xx}=(4p^2-3p-2)/D L q q † = L xx † = ( 4 p 2 − 3 p − 2 ) / D for every vertex.
Proof. For v = q ∈ Q 0 v=q\in Q_0 v = q ∈ Q 0 , denote the values of φ = L † e q \varphi=L^\dagger e_q φ = L † e q on the five orbits { q } \{q\} { q } , Q 0 ∖ { q } Q_0\setminus\{q\} Q 0 ∖ { q } , X 0 X_0 X 0 , X 1 X_1 X 1 and Q 1 Q_1 Q 1 by α , κ , α , ε \alpha,\kappa,\alpha,\varepsilon α , κ , α , ε and ζ \zeta ζ . A vertex in Q 0 ∖ { q } Q_0\setminus\{q\} Q 0 ∖ { q } is adjacent to q q q , to p − 2 p-2 p − 2 other vertices in Q 0 Q_0 Q 0 and to all p p p vertices of X 0 X_0 X 0 ; a vertex in X 0 X_0 X 0 is adjacent to q q q , to the p − 1 p-1 p − 1 vertices of Q 0 ∖ { q } Q_0\setminus\{q\} Q 0 ∖ { q } , to h − 1 h-1 h − 1 vertices in X 0 X_0 X 0 and to h − 1 h-1 h − 1 vertices in X 1 X_1 X 1 ; and similarly on block 1. Writing out ( L φ ) w = δ q w − 1 / ( 4 p ) (L\varphi)_w=\delta_{qw}-1/(4p) ( L φ ) w = δ q w − 1/ ( 4 p ) on each orbit together with 1 ⊤ φ = 0 \mathbf{1}^{\top}\varphi=0 1 ⊤ φ = 0 gives
( 2 p − 1 ) a − ( p − 1 ) κ − p α = 1 − 1 4 p , ( 2 p − 1 ) κ − a − ( p − 2 ) κ − p α = − 1 4 p , ( 2 p − 2 ) α − a − ( p − 1 ) κ − ( h − 1 ) α − ( h − 1 ) ε = − 1 4 p , ( 2 p − 2 ) ε − p ζ − ( h − 1 ) ε − ( h − 1 ) α = − 1 4 p , ( 2 p − 1 ) ζ − ( p − 1 ) ζ − p ε = − 1 4 p , a + ( p − 1 ) κ + p α + p ε + p ζ = 0. \begin{aligned}
(2p-1)a-(p-1)\kappa-p\alpha&=1-\frac{1}{4p},&
(2p-1)\kappa-a-(p-2)\kappa-p\alpha&=-\frac{1}{4p},\\
(2p-2)\alpha-a-(p-1)\kappa-(h-1)\alpha-(h-1)\varepsilon&=-\frac{1}{4p},\\
(2p-2)\varepsilon-p\zeta-(h-1)\varepsilon-(h-1)\alpha&=-\frac{1}{4p},\\
(2p-1)\zeta-(p-1)\zeta-p\varepsilon&=-\frac{1}{4p},&
a+(p-1)\kappa+p\alpha+p\varepsilon+p\zeta&=0.
\end{aligned} ( 2 p − 1 ) a − ( p − 1 ) κ − p α ( 2 p − 2 ) α − a − ( p − 1 ) κ − ( h − 1 ) α − ( h − 1 ) ε ( 2 p − 2 ) ε − pζ − ( h − 1 ) ε − ( h − 1 ) α ( 2 p − 1 ) ζ − ( p − 1 ) ζ − pε = 1 − 4 p 1 , = − 4 p 1 , = − 4 p 1 , = − 4 p 1 , ( 2 p − 1 ) κ − a − ( p − 2 ) κ − p α a + ( p − 1 ) κ + p α + pε + pζ = − 4 p 1 , = 0.
Subtracting the second equation from the first immediately gives a − κ = 1 / ( 2 p ) a-\kappa=1/(2p) a − κ = 1/ ( 2 p ) , and solving the remaining linear equations yields the five values in the left-hand table of Lemma 4.5 .
For v = x = x 0 , c , t ∈ X 0 ∩ Y c v=x=x_{0,c,t}\in X_0\cap Y_c v = x = x 0 , c , t ∈ X 0 ∩ Y c , the eight stabiliser orbits are listed in the right-hand table of Lemma 4.5 . Counting neighbours between orbits directly from Definition 4.3 (for instance, a vertex x 0 , c , t ′ ∈ ( X 0 ∩ Y c ) ∖ { x } x_{0,c,t'}\in(X_0\cap Y_c)\setminus\{x\} x 0 , c , t ′ ∈ ( X 0 ∩ Y c ) ∖ { x } is adjacent to all p p p vertices of Q 0 Q_0 Q 0 , to x x x , to the remaining h − 2 h-2 h − 2 vertices of X 0 ∩ Y c X_0\cap Y_c X 0 ∩ Y c , to the h − 2 h-2 h − 2 vertices x 1 , c , t ′ ′ x_{1,c,t''} x 1 , c , t ′′ with t ′ ′ ∉ { t , t ′ } t''\notin\{t,t'\} t ′′ ∈ / { t , t ′ } , and to the partner x 1 , c , t x_{1,c,t} x 1 , c , t ) produces eight linear equations from L φ = e x − 1 / ( 4 p ) L\varphi=e_x-1/(4p) L φ = e x − 1/ ( 4 p ) along with 1 ⊤ φ = 0 \mathbf{1}^{\top}\varphi=0 1 ⊤ φ = 0 , whose unique solution is given in the right-hand table. Finally, since L u u † = L v v † = ( 4 p 2 − 3 p − 2 ) / D L^\dagger_{uu}=L^\dagger_{vv}=(4p^2-3p-2)/D L uu † = L v v † = ( 4 p 2 − 3 p − 2 ) / D for all w , v ∈ V w,v\in V w , v ∈ V , substituting L u v † L^\dagger_{uv} L uv † into (1) gives the effective resistances in the last column.
Proof of Theorem B
Proof of Theorem B. Let G = F ( p ) G=\mathcal{F}(p) G = F ( p ) with p ≥ 4 p\ge4 p ≥ 4 even. As noted after Definition 4.3 , G G G has n = 4 p n=4p n = 4 p vertices, 2 p 2p 2 p of degree 2 p − 1 2p-1 2 p − 1 (in Q 0 ∪ Q 1 Q_0\cup Q_1 Q 0 ∪ Q 1 ) and 2 p 2p 2 p of degree 2 p − 2 2p-2 2 p − 2 (in X 0 ∪ X 1 X_0\cup X_1 X 0 ∪ X 1 ). By Lemma 4.4 , G G G is a bi-Cayley graph over H H H , and every class of nontrivial characters in the table of that lemma has Θ > 0 \Theta>0 Θ > 0 because p ≥ 4 p\ge4 p ≥ 4 , so G G G is connected by Lemma 4.2 . Multiplying the last column of the table by the number of characters in each class and summing gives − 1 / p + 1 / ( 2 p ) + ( p − 1 ) / ( 2 p ( p − 1 ) ) = 0 -1/p+1/(2p)+(p-1)/(2p(p-1))=0 − 1/ p + 1/ ( 2 p ) + ( p − 1 ) / ( 2 p ( p − 1 )) = 0 , so (10) holds and G G G is resistance-regular by Lemma 4.2 . Substituting ∣ H ∣ = 2 p \lvert H\rvert=2p ∣ H ∣ = 2 p , ∣ S 12 ∣ = p \lvert S_{12}\rvert=p ∣ S 12 ∣ = p and the values of M 22 / Θ M_{22}/\Theta M 22 /Θ from the table into (8) gives L v v † = 1 / ( 8 p 2 ) + ( 1 + 1 / ( p − 2 ) ) / ( 2 p ) = ( 4 p 2 − 3 p − 2 ) / ( 8 p 2 ( p − 2 ) ) L^\dagger_{vv}=1/(8p^2)+(1+1/(p-2))/(2p)=(4p^2-3p-2)/(8p^2(p-2)) L v v † = 1/ ( 8 p 2 ) + ( 1 + 1/ ( p − 2 )) / ( 2 p ) = ( 4 p 2 − 3 p − 2 ) / ( 8 p 2 ( p − 2 )) . By (2) and tr L † = 4 p L v v † \operatorname{tr}L^\dagger=4pL^\dagger_{vv} tr L † = 4 p L v v † , every vertex has resistance degree R v = ( 4 p 2 − 3 p − 2 ) / ( p ( p − 2 ) ) R_v=(4p^2-3p-2)/(p(p-2)) R v = ( 4 p 2 − 3 p − 2 ) / ( p ( p − 2 )) , and Kf ( G ) = 2 ( 4 p 2 − 3 p − 2 ) / ( p − 2 ) \operatorname{Kf}(G)=2(4p^2-3p-2)/(p-2) Kf ( G ) = 2 ( 4 p 2 − 3 p − 2 ) / ( p − 2 ) .
The Laplacian spectrum consists of the eigenvalues of the blocks L ^ χ \widehat{L}_\chi L χ . The trivial character gives L ^ 1 = p ( 1 − 1 − 1 1 ) \widehat{L}_1=p\begin{pmatrix}1&-1\\-1&1\end{pmatrix} L 1 = p ( 1 − 1 − 1 1 ) , with eigenvalues 0 0 0 and 2 p 2p 2 p . For ( α , γ , k ) = ( 0 , 1 , 0 ) (\alpha,\gamma,k)=(0,1,0) ( α , γ , k ) = ( 0 , 1 , 0 ) , the block ( 2 p − 2 − p − p p ) \begin{pmatrix}2p-2&-p\\-p&p\end{pmatrix} ( 2 p − 2 − p − p p ) has trace 3 p − 2 3p-2 3 p − 2 and determinant p ( p − 2 ) p(p-2) p ( p − 2 ) , so its eigenvalues are ρ ± = 1 2 ( 3 p − 2 ± s ) \rho_\pm=\frac{1}{2}(3p-2\pm s) ρ ± = 2 1 ( 3 p − 2 ± s ) with s = 5 p 2 − 4 p + 4 s=\sqrt{5p^2-4p+4} s = 5 p 2 − 4 p + 4 . The remaining four classes have χ ( S 12 ) = 0 \chi(S_{12})=0 χ ( S 12 ) = 0 , so their blocks are diagonal with diagonal entries ( p , 2 p ) (p,2p) ( p , 2 p ) , ( 2 p − 2 , 2 p ) (2p-2,2p) ( 2 p − 2 , 2 p ) (occurring p − 2 p-2 p − 2 times) and ( 2 p − 2 , 2 p ) (2p-2,2p) ( 2 p − 2 , 2 p ) (occurring p − 2 p-2 p − 2 times). Hence the Laplacian spectrum of G G G is
0 ( 1 ) , p ( 1 ) , ρ − ( 1 ) , ρ + ( 1 ) , ( 2 p − 2 ) ( p − 1 ) , ( 2 p ) ( 3 p − 3 ) , (11) 0^{(1)},\quad p^{(1)},\quad\rho_-^{(1)},\quad\rho_+^{(1)},\quad(2p-2)^{(p-1)},\quad(2p)^{(3p-3)}, \tag*{(11)} 0 ( 1 ) , p ( 1 ) , ρ − ( 1 ) , ρ + ( 1 ) , ( 2 p − 2 ) ( p − 1 ) , ( 2 p ) ( 3 p − 3 ) , (11)
where exponents denote multiplicities. Since s 2 − ( 2 p ) 2 = ( p − 2 ) 2 > 0 s^2-(2p)^2=(p-2)^2>0 s 2 − ( 2 p ) 2 = ( p − 2 ) 2 > 0 , we have s > 2 p s>2p s > 2 p , so ρ + > ( 5 p − 2 ) / 2 > 2 p \rho_+>(5p-2)/2>2p ρ + > ( 5 p − 2 ) /2 > 2 p and ρ − < ( p − 2 ) / 2 < p \rho_-<(p-2)/2<p ρ − < ( p − 2 ) /2 < p , while ρ − > 0 \rho_->0 ρ − > 0 because ρ + ρ − = p ( p − 2 ) > 0 \rho_+\rho_-=p(p-2)>0 ρ + ρ − = p ( p − 2 ) > 0 . Together with p < 2 p − 2 < 2 p p<2p-2<2p p < 2 p − 2 < 2 p , this gives 0 < ρ − < p < 2 p − 2 < 2 p < ρ + 0<\rho_-<p<2p-2<2p<\rho_+ 0 < ρ − < p < 2 p − 2 < 2 p < ρ + , so G G G has exactly five distinct nonzero Laplacian eigenvalues.
Finally, the translation by ( 0 , 1 , 0 ) ∈ H (0,1,0)\in H ( 0 , 1 , 0 ) ∈ H exchanges the two blocks, so every vertex is equivalent under an automorphism to a vertex of Q 0 Q_0 Q 0 or of X 0 X_0 X 0 . By Lemma 4.5 , every effective resistance between distinct vertices of G G G is therefore one of the rational functions of p p p in the last columns of the two tables of that lemma. The values ( 2 p + 1 ) / ( 2 p 2 ) (2p+1)/(2p^2) ( 2 p + 1 ) / ( 2 p 2 ) and ( 2 p 2 + p − 2 ) / ( 2 p 2 ( p − 2 ) ) (2p^2+p-2)/(2p^2(p-2)) ( 2 p 2 + p − 2 ) / ( 2 p 2 ( p − 2 )) occur in both tables, so there are four of these functions on edges and five on non-edges, and the nine functions are pairwise distinct for every even p ≥ 4 p\ge4 p ≥ 4 .
For p = 4 , 6 , 8 , 10 p=4,6,8,10 p = 4 , 6 , 8 , 10 , Theorem B gives L v v † = 25 / 128 L^\dagger_{vv}=25/128 L v v † = 25/128 , 31 / 288 31/288 31/288 , 115 / 1536 115/1536 115/1536 and 23 / 400 23/400 23/400 , and graphs 1, 4 and 13 of Table 2 are F ( 4 ) \mathcal{F}(4) F ( 4 ) , F ( 6 ) \mathcal{F}(6) F ( 6 ) and F ( 8 ) \mathcal{F}(8) F ( 8 ) . The tables of Lemma 4.5 also give a second, combinatorial proof of resistance-regularity, and they explain how the two degree classes balance.
Corollary 4.6. In F ( p ) \mathcal{F}(p) F ( p ) , ∑ u ∼ q r u q = ∑ u ∼ x r u x = 2 − 2 / ( 4 p ) \sum_{u\sim q} r_{uq}=\sum_{u\sim x} r_{ux}=2-2/(4p) ∑ u ∼ q r u q = ∑ u ∼ x r ux = 2 − 2/ ( 4 p ) for q ∈ Q b q\in Q_b q ∈ Q b and x ∈ X b x\in X_b x ∈ X b ; by Theorem 2.4 (iii), this gives a second proof that F ( p ) \mathcal{F}(p) F ( p ) is resistance-regular.
The two sums in Corollary 4.6 follow from Lemma 4.5 and show how F ( p ) \mathcal{F}(p) F ( p ) achieves constant resistance degree despite having two different vertex degrees. Every vertex, whether in Q b Q_b Q b or in X b X_b X b , is incident to p p p cross-edges between Q b Q_b Q b and X b X_b X b , and each such edge has resistance ( 2 p + 1 ) / ( 2 p 2 ) (2p+1)/(2p^2) ( 2 p + 1 ) / ( 2 p 2 ) , contributing ( 2 p + 1 ) / ( 2 p ) (2p+1)/(2p) ( 2 p + 1 ) / ( 2 p ) to both sums. The remaining incident edges are the p − 1 p-1 p − 1 clique edges at q ∈ Q b q\in Q_b q ∈ Q b and the p − 2 = 2 ( h − 1 ) p-2=2(h-1) p − 2 = 2 ( h − 1 ) cocktail-party edges at x ∈ X b x\in X_b x ∈ X b . Their contributions match because of the identity
( p − 1 ) ⋅ 1 p = ( h − 1 ) ( 2 p − 1 2 p ( p − 1 ) + 2 p 2 − 3 p + 2 2 p ( p − 1 ) ( p − 2 ) ) = p − 1 p . (12) (p-1)\cdot\frac{1}{p}=(h-1)\left(\frac{2p-1}{2p(p-1)}+\frac{2p^2-3p+2}{2p(p-1)(p-2)}\right)=\frac{p-1}{p}. \tag*{(12)} ( p − 1 ) ⋅ p 1 = ( h − 1 ) ( 2 p ( p − 1 ) 2 p − 1 + 2 p ( p − 1 ) ( p − 2 ) 2 p 2 − 3 p + 2 ) = p p − 1 . (12)
In view of (3) , equation (12) states that in a uniformly random spanning tree of F ( p ) \mathcal{F}(p) F ( p ) , the expected number of incident clique edges at a vertex of Q b Q_b Q b equals the expected number of incident Y c Y_c Y c -edges at a vertex of X b X_b X b : the p − 2 p-2 p − 2 edges of Y c Y_c Y c at x x x are fewer in number than the p − 1 p-1 p − 1 clique edges at q q q , but each carries a slightly higher spanning-tree probability because the removed matching in Y c Y_c Y c forces current between the two blocks to pass through them. Note also that the value r q q ′ = 1 / p r_{qq'}=1/p r q q ′ = 1/ p on a clique edge has a transparent electrical reason: any two vertices q , q ′ ∈ Q b q,q'\in Q_b q , q ′ ∈ Q b are true twins, so when unit current flows from q q q to q ′ q' q ′ every other vertex stays at the midpoint potential, and the direct edge q q ′ qq' q q ′ acts in parallel with 2 p − 2 2p-2 2 p − 2 two-step paths through common neighbours, giving resistance 1 / ( 1 + ( 2 p − 2 ) / 2 ) = 1 / p 1/(1+(2p-2)/2)=1/p 1/ ( 1 + ( 2 p − 2 ) /2 ) = 1/ p .
Example 4.7 (The sixteen-vertex graph F ( 4 ) \mathcal{F}(4) F ( 4 ) ). The smallest member F ( 4 ) \mathcal{F}(4) F ( 4 ) has 16 vertices and 52 edges, eight vertices of degree 6 and eight of degree 7. It is drawn in Figure 2 with Q 0 = { 8 , 9 , 10 , 11 } Q_0=\{8,9,10,11\} Q 0 = { 8 , 9 , 10 , 11 } , Q 1 = { 12 , 13 , 14 , 15 } Q_1=\{12,13,14,15\} Q 1 = { 12 , 13 , 14 , 15 } , X 0 = { 0 , 1 , 4 , 5 } X_0=\{0,1,4,5\} X 0 = { 0 , 1 , 4 , 5 } and X 1 = { 2 , 3 , 6 , 7 } X_1=\{2,3,6,7\} X 1 = { 2 , 3 , 6 , 7 } , where Y 0 = { 0 , 1 , 2 , 3 } Y_0=\{0,1,2,3\} Y 0 = { 0 , 1 , 2 , 3 } and Y 1 = { 4 , 5 , 6 , 7 } Y_1=\{4,5,6,7\} Y 1 = { 4 , 5 , 6 , 7 } induce 4-cycles. Here L v v † = 25 / 128 L^\dagger_{vv}=25/128 L v v † = 25/128 , R v = 25 / 4 R_v=25/4 R v = 25/4 and Kf ( F ( 4 ) ) = 50 \operatorname{Kf}(\mathcal{F}(4))=50 Kf ( F ( 4 )) = 50 ; the Laplacian eigenvalues are 0, 4, 6 ( 3 ) 6^{(3)} 6 ( 3 ) , 8 ( 9 ) 8^{(9)} 8 ( 9 ) and 5 ± 17 5\pm\sqrt{17} 5 ± 17 , and F ( 4 ) \mathcal{F}(4) F ( 4 ) has τ = 2 31 ⋅ 3 3 \tau=2^{31}\cdot3^3 τ = 2 31 ⋅ 3 3 spanning trees, in accordance with Proposition 2.5 . By Lemma 4.5 , the resistances on edges are 1 / 4 1/4 1/4 , 9 / 32 9/32 9/32 , 7 / 24 7/24 7/24 and 11 / 24 11/24 11/24 , and those on non-edges are 17 / 48 17/48 17/48 , 1 / 2 1/2 1/2 , 25 / 48 25/48 25/48 , 17 / 32 17/32 17/32 and 9 / 16 9/16 9/16 . Thus r u v r_{uv} r uv determines whether u v uv uv is an edge, but no threshold on r u v r_{uv} r uv separates edges from non-edges. The automorphism group of F ( 4 ) \mathcal{F}(4) F ( 4 ) has order 9216, and its orbits are the two degree classes.
Figure 2. The graph F ( 4 ) \mathcal{F}(4) F ( 4 ) . Filled vertices form the two cliques Q 0 Q_0 Q 0 and Q 1 Q_1 Q 1 (degree 7), hollow vertices the outer sets X 0 = { 0 , 1 , 4 , 5 } X_0=\{0,1,4,5\} X 0 = { 0 , 1 , 4 , 5 } and X 1 = { 2 , 3 , 6 , 7 } X_1=\{2,3,6,7\} X 1 = { 2 , 3 , 6 , 7 } (degree 6). Thin grey lines are the complete joins Q 0 Q_0 Q 0 –X 0 X_0 X 0 and Q 1 Q_1 Q 1 –X 1 X_1 X 1 ; the heavy squares are the 4-cycles induced by Y 0 Y_0 Y 0 and Y 1 Y_1 Y 1 .
A four-parameter family. The graph F ( p ) \mathcal{F}(p) F ( p ) is a special case of a larger construction. For integers s , a , k ≥ 1 s,a,k\ge1 s , a , k ≥ 1 and h ≥ 2 h\ge2 h ≥ 2 , take s s s disjoint cliques Q b ≅ K a Q_b\cong K_a Q b ≅ K a (b < s b<s b < s ), join each Q b Q_b Q b completely to a set X b X_b X b of k h kh k h new vertices x b , c , t x_{b,c,t} x b , c , t (c < k c<k c < k , t < h t<h t < h ), and join x b , c , t x_{b,c,t} x b , c , t and x b ′ , c ′ , t ′ x_{b',c',t'} x b ′ , c ′ , t ′ whenever $c=c and t ≠ t ′ t \ne t' t = t ′ . Writing G ( s , a , k , h ) \mathcal{G}(s,a,k,h) G ( s , a , k , h ) for this graph, we have F ( p ) = G ( 2 , p , 2 , p / 2 ) \mathcal{F}(p)=\mathcal{G}(2,p,2,p/2) F ( p ) = G ( 2 , p , 2 , p /2 ) . In Appendix § 9 we compute the Laplacian spectrum of G ( s , a , k , h ) \mathcal{G}(s,a,k,h) G ( s , a , k , h ) and show that it is resistance-regular if and only if a single polynomial N ( s , a , k , h ) N(s,a,k,h) N ( s , a , k , h ) vanishes. The integer solutions include a two-parameter family in which the two degrees differ by 2 s − 3 2s-3 2 s − 3 ; since the constructions of § 6 give larger differences, we do not pursue this family in the main text.
How sharp Theorem A is
The graphs F ( p ) \mathcal{F}(p) F ( p ) have m = 5 m=5 m = 5 distinct nonzero Laplacian eigenvalues. Graphs 14 and 15 of Table 2 have one fewer.
Proposition 4.8. There exist non-regular resistance-regular graphs whose Laplacian has m = 4 m=4 m = 4 distinct nonzero eigenvalues.
Proof. Let G G G be graph 14 (or graph 15) of Table 2 , defined as a bi-Cayley graph over Z 4 × Z 4 \mathbb{Z}_4 \times\mathbb{Z}_4 Z 4 × Z 4 by the connection sets in Appendix § 10 . It has 32 vertices of degrees 14 and 15, and exact rational inversion of L + J / 32 L+J/32 L + J /32 confirms that L v v † = 37 / 512 L^\dagger_{vv}=37/512 L v v † = 37/512 for every vertex v v v . Its Laplacian characteristic polynomial is
x ( x − 12 ) 6 ( x − 16 ) 23 ( x 2 − 24 x + 64 ) , x(x-12)^6(x-16)^{23}(x^2-24x+64), x ( x − 12 ) 6 ( x − 16 ) 23 ( x 2 − 24 x + 64 ) , so its nonzero Laplacian eigenvalues are 12, 16 and 12 ± 4 5 12\pm4\sqrt{5} 12 ± 4 5 , which are four distinct values. □
Hence, for m = 4 m=4 m = 4 and m = 5 m=5 m = 5 , the conditions in Theorem A(i) cannot be reduced to the first one, even if only regularity, rather than walk-regularity, is required. For m = 3 m=3 m = 3 , Theorem A(ii) leaves room for two distinct degrees, and we do not know whether a non-regular resistance-regular graph with m = 3 m=3 m = 3 exists. Whether the first two conditions in Theorem A(i) always force regularity is discussed in § 7.1 .
Modules and blow-ups
The proofs in § 4 used one structural feature of F ( p ) \mathcal{F}(p) F ( p ) repeatedly: the vertices of each clique Q b Q_b Q b are true twins, so every permutation of Q b Q_b Q b is an automorphism and the potentials inside Q b Q_b Q b are easy to control. In this section we turn this observation into a general method, which we use in § 6 to prove Theorem C. We show that the diagonal entry L v v † L^\dagger_{vv} L v v † at a vertex v v v of a module splits into a part that depends only on the module itself and a part that depends only on how the module is attached to the rest of the graph (Lemma 5.2 ). For graphs built entirely from cliques and independent sets, resistance-regularity then becomes a system of rational equations in the sizes of these sets.
Definition 5.1 (module, blow-up). A set M ⊆ V M\subseteq V M ⊆ V is a module of G G G if every vertex outside M M M is adjacent either to all vertices of M M M or to none of them. Given a connected graph H H H on the vertex set { 1 , … , r } \{1,\ldots,r\} { 1 , … , r } and graphs W 1 , … , W r W_1,\ldots,W_r W 1 , … , W r , the blow-up H [ W 1 , … , W r ] H[W_1,\ldots,W_r] H [ W 1 , … , W r ] is obtained from the disjoint union of W 1 , … , W r W_1,\ldots,W_r W 1 , … , W r by joining every vertex of W i W_i W i to every vertex of W j W_j W j whenever i j ij ij is an edge of H H H .
The vertex sets M i = V ( W i ) M_i=V(W_i) M i = V ( W i ) of a blow-up are modules, which we call the modules of the blow-up. We write K m K_m K m for the complete graph and K ‾ m \overline{K}_m K m for the edgeless graph on m m m vertices; the vertices of a module inducing K m K_m K m are true twins (they have the same closed neighbourhood), and those of a module inducing K ‾ m \overline{K}_m K m are false twins (they have the same open neighbourhood).
Lemma 5.2. Let G G G be a connected graph on n n n vertices, let M ≠ V M\ne V M = V be a module of G G G with ∣ M ∣ = m |M|=m ∣ M ∣ = m and W = G [ M ] W=G[M] W = G [ M ] , and let c ≥ 1 c\ge1 c ≥ 1 be the number of vertices outside M M M that are adjacent
to M M M . Write L W L_W L W for the Laplacian of W W W and 1 M \mathbf{1}_M 1 M for the indicator vector of M M M . Then for every v ∈ M v \in M v ∈ M ,
L v v † = [ ( L W + c I ) − 1 ] v v − 1 c m + 1 M ⊤ L † 1 M m 2 , (13) L^\dagger_{vv} = \left[(L_W+cI)^{-1}\right]_{vv} - \frac{1}{cm} + \frac{\mathbf{1}_M^\top L^\dagger\mathbf{1}_M}{m^2}, \tag*{(13)} L v v † = [ ( L W + c I ) − 1 ] v v − c m 1 + m 2 1 M ⊤ L † 1 M , (13)
( ( L † ) 2 ) v v = ∥ ( L W + c I ) − 1 ( e v − 1 M m ) ∥ 2 + ∥ L † 1 M ∥ 2 m 2 . (14) \left((L^\dagger)^2\right)_{vv} = \left\|(L_W+cI)^{-1}\left(e_v-\frac{\mathbf{1}_M}{m}\right)\right\|^2 + \frac{\|L^\dagger\mathbf{1}_M\|^2}{m^2}. \tag*{(14)} ( ( L † ) 2 ) v v = ( L W + c I ) − 1 ( e v − m 1 M ) 2 + m 2 ∥ L † 1 M ∥ 2 . (14)
If W W W is walk-regular, then L v v † L^\dagger_{vv} L v v † and ( ( L † ) 2 ) v v \left((L^\dagger)^2\right)_{vv} ( ( L † ) 2 ) v v take the same value at all vertices of M M M , and
[ ( L W + c I ) − 1 ] v v − 1 c m = 1 m ∑ ν 1 ν + c , \left[(L_W+cI)^{-1}\right]_{vv}-\frac{1}{cm}=\frac{1}{m}\sum_{\nu}\frac{1}{\nu+c}, [ ( L W + c I ) − 1 ] v v − c m 1 = m 1 ν ∑ ν + c 1 ,
where ν \nu ν runs over all Laplacian eigenvalues of W W W , with multiplicity, except for one eigenvalue 0 0 0 .
Proof. Let U U U be the space of vectors supported on M M M whose entries sum to zero. For z ∈ U z \in U z ∈ U and a vertex w ∉ M w \notin M w ∈ / M , ( L z ) w = − ∑ u ∼ w z u (Lz)_w=-\sum_{u\sim w}z_u ( L z ) w = − ∑ u ∼ w z u is either 0 0 0 or − ∑ u ∈ M z u = 0 -\sum_{u\in M}z_u=0 − ∑ u ∈ M z u = 0 , because w w w is adjacent to all of M M M or to none of it; and for w ∈ M w \in M w ∈ M , ( L z ) w = ( ( L W + c I ) z ) w (Lz)_w=((L_W+cI)z)_w ( L z ) w = (( L W + c I ) z ) w , because w w w has exactly c c c neighbours outside M M M , at which z z z vanishes. Hence U U U is invariant under L L L , and L L L acts on U U U as L W + c I L_W+cI L W + c I , which is invertible because c ≥ 1 c\ge1 c ≥ 1 . Since L L L is symmetric and U ⊆ 1 ⊥ U\subseteq\mathbf{1}^{\perp} U ⊆ 1 ⊥ , the space U ⊥ U^\perp U ⊥ is also invariant, so L † L^\dagger L † maps U U U to itself, acting there as ( L W + c I ) − 1 (L_W+cI)^{-1} ( L W + c I ) − 1 , and maps U ⊥ U^\perp U ⊥ to itself. Write e v = z + 1 M / m e_v=z+\mathbf{1}_M/m e v = z + 1 M / m with z = e v − 1 M / m ∈ U z=e_v-\mathbf{1}_M/m\in U z = e v − 1 M / m ∈ U , and note that 1 M ∈ U ⊥ \mathbf{1}_M\in U^\perp 1 M ∈ U ⊥ . Then L v v † = z ⊤ L † z + 1 M ⊤ L † 1 M / m 2 L^\dagger_{vv}=z^\top L^\dagger z+\mathbf{1}_M^\top L^\dagger\mathbf{1}_M/m^2 L v v † = z ⊤ L † z + 1 M ⊤ L † 1 M / m 2 and ( ( L † ) 2 ) v v = ∥ L † e v ∥ 2 = ∥ L † z ∥ 2 + ∥ L † 1 M ∥ 2 / m 2 \left((L^\dagger)^2\right)_{vv}=\|L^\dagger e_v\|^2=\|L^\dagger z\|^2+\|L^\dagger\mathbf{1}_M\|^2/m^2 ( ( L † ) 2 ) v v = ∥ L † e v ∥ 2 = ∥ L † z ∥ 2 + ∥ L † 1 M ∥ 2 / m 2 , the cross terms vanishing because L † z ∈ U L^\dagger z\in U L † z ∈ U and L † 1 M ∈ U ⊥ L^\dagger\mathbf{1}_M\in U^\perp L † 1 M ∈ U ⊥ . Finally, L W 1 M = 0 L_W\mathbf{1}_M=0 L W 1 M = 0 gives ( L W + c I ) − 1 1 M = 1 M / c (L_W+cI)^{-1}\mathbf{1}_M=\mathbf{1}_M/c ( L W + c I ) − 1 1 M = 1 M / c , so that z ⊤ ( L W + c I ) − 1 z = [ ( L W + c I ) − 1 ] v v − 2 / ( c m ) + 1 / ( c m ) z^\top(L_W+cI)^{-1}z=[(L_W+cI)^{-1}]_{vv}-2/(cm)+1/(cm) z ⊤ ( L W + c I ) − 1 z = [( L W + c I ) − 1 ] v v − 2/ ( c m ) + 1/ ( c m ) , which proves (13) ; (14) is ∥ L † z ∥ 2 = ∥ ( L W + c I ) − 1 z ∥ 2 \|L^\dagger z\|^2=\|(L_W+cI)^{-1}z\|^2 ∥ L † z ∥ 2 = ∥ ( L W + c I ) − 1 z ∥ 2 .
If W W W is walk-regular of degree d d d , then L W = d I − A W L_W=dI-A_W L W = d I − A W , so ( L W + c I ) − 1 (L_W+cI)^{-1} ( L W + c I ) − 1 and ( L W + c I ) − 2 (L_W+cI)^{-2} ( L W + c I ) − 2 are polynomials in A W A_W A W and have constant diagonals; the remaining terms in (13) and (14) do not depend on v ∈ M v\in M v ∈ M . The constant diagonal of ( L W + c I ) − 1 (L_W+cI)^{-1} ( L W + c I ) − 1 equals 1 m tr ( L W + c I ) − 1 = 1 m ∑ ν ′ 1 ν ′ + c \frac{1}{m}\operatorname{tr}(L_W+cI)^{-1}=\frac{1}{m}\sum_{\nu'}\frac{1}{\nu'+c} m 1 tr ( L W + c I ) − 1 = m 1 ∑ ν ′ ν ′ + c 1 , the sum running over all Laplacian eigenvalues ν ′ \nu' ν ′ of W W W ; removing one eigenvalue 0 0 0 cancels the term 1 / ( c m ) 1/(cm) 1/ ( c m ) .
For a clique module K m K_m K m the sum in Lemma 5.2 consists of m − 1 m-1 m − 1 terms 1 / ( m + c ) 1/(m+c) 1/ ( m + c ) , and for an independent module K m ‾ \overline{K_m} K m of m − 1 m-1 m − 1 terms 1 / c 1/c 1/ c . We now combine the lemma over all modules of a blow-up. Let H H H be a connected graph on { 1 , … , r } \{1,\ldots,r\} { 1 , … , r } with r ≥ 2 r\ge2 r ≥ 2 , let m 1 , … , m r ≥ 1 m_1,\ldots,m_r\ge1 m 1 , … , m r ≥ 1 , let each W i W_i W i be K m i K_{m_i} K m i or K ‾ m i \overline{K}_{m_i} K m i , and let G = H [ W 1 , … , W r ] G=H[W_1,\ldots,W_r] G = H [ W 1 , … , W r ] , so that n = m 1 + ⋯ + m r n=m_1+\cdots+m_r n = m 1 + ⋯ + m r . For each i i i put
c i = ∑ j ∼ i m j , λ i = { c i + m i if W i = K m i , c i if W i = K ‾ m i , c_i=\sum_{j\sim i}m_j,\qquad
\lambda_i=
\begin{cases}
c_i+m_i & \text{if } W_i=K_{m_i},\\
c_i & \text{if } W_i=\overline{K}_{m_i},
\end{cases} c i = j ∼ i ∑ m j , λ i = { c i + m i c i if W i = K m i , if W i = K m i ,
so that a vertex of M i M_i M i has degree λ i − 1 \lambda_i-1 λ i − 1 if M i M_i M i is a clique and λ i \lambda_i λ i if it is independent.
Proposition 5.3. For each i i i , the linear system
∑ k ∼ j m k ( y j − y k ) = δ i j − m i n ( 1 ≤ j ≤ r ) , ∑ j = 1 r m j y j = 0 , (15) \sum_{k\sim j}m_k(y_j-y_k)=\delta_{ij}-\frac{m_i}{n}\quad(1\le j\le r),\qquad\sum_{j=1}^{r}m_jy_j=0, \tag*{(15)} k ∼ j ∑ m k ( y j − y k ) = δ ij − n m i ( 1 ≤ j ≤ r ) , j = 1 ∑ r m j y j = 0 , (15) has a unique solution y ( i ) ∈ R r y^{(i)}\in\mathbb{R}^r y ( i ) ∈ R r , and for every vertex v ∈ M i v\in M_i v ∈ M i ,
L v v † = m i − 1 m i λ i + y i ( i ) m i , ( ( L † ) 2 ) v v = m i − 1 m i λ i 2 + 1 m i 2 ∑ j = 1 r m j ( y j ( i ) ) 2 . L^\dagger_{vv}=\frac{m_i-1}{m_i\lambda_i}+\frac{y_i^{(i)}}{m_i},\qquad
\left((L^\dagger)^2\right)_{vv}=\frac{m_i-1}{m_i\lambda_i^2}+\frac{1}{m_i^2}\sum_{j=1}^{r}m_j\left(y_j^{(i)}\right)^2. L v v † = m i λ i m i − 1 + m i y i ( i ) , ( ( L † ) 2 ) v v = m i λ i 2 m i − 1 + m i 2 1 j = 1 ∑ r m j ( y j ( i ) ) 2 . In particular, G G G is resistance-regular if and only if ( m i − 1 ) / ( m i λ i ) + y i ( i ) / m i (m_i-1)/(m_i\lambda_i)+y_i^{(i)}/m_i ( m i − 1 ) / ( m i λ i ) + y i ( i ) / m i takes the same value for all i i i .
Proof. A vector that is constant on every module, with value y j y_j y j on M j M_j M j , is mapped by L L L to the vector whose value on M j M_j M j is ∑ k ∼ j m k ( y j − y k ) \sum_{k\sim j}m_k(y_j-y_k) ∑ k ∼ j m k ( y j − y k ) , because the edges inside a module do not contribute. Hence the space of such vectors is invariant under L L L , and so is its intersection with 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ , on which L L L is invertible. The vector 1 M i − ( m i / n ) 1 \mathbf{1}_{M_i}-(m_i/n)\mathbf{1} 1 M i − ( m i / n ) 1 lies in this intersection, so L † 1 M i L^{\dagger}\mathbf{1}_{M_i} L † 1 M i is constant on every module; writing y j y_j y j for its value on M j M_j M j , the equations L L † 1 M i = 1 M i − ( m i / n ) 1 LL^{\dagger}\mathbf{1}_{M_i}=\mathbf{1}_{M_i}-(m_i/n)\mathbf{1} L L † 1 M i = 1 M i − ( m i / n ) 1 and 1 ⊤ L † 1 M i = 0 \mathbf{1}^{\top}L^{\dagger}\mathbf{1}_{M_i}=0 1 ⊤ L † 1 M i = 0 are exactly (15) . The solution is unique, because the difference of two solutions corresponds to a vector in the kernel of L L L , which is constant and orthogonal to 1 \mathbf{1} 1 , hence zero. Now 1 M i ⊤ L † 1 M i = m i y i ( i ) \mathbf{1}_{M_i}^{\top}L^{\dagger}\mathbf{1}_{M_i}=m_i y_i^{(i)} 1 M i ⊤ L † 1 M i = m i y i ( i ) and ∥ L † 1 M i ∥ 2 = ∑ j m j ( y j ( i ) ) 2 \lVert L^{\dagger}\mathbf{1}_{M_i}\rVert^2=\sum_jm_j(y_j^{(i)})^2 ∥ L † 1 M i ∥ 2 = ∑ j m j ( y j ( i ) ) 2 , and the first terms of (13) and (14) equal ( m i − 1 ) / ( m i λ i ) (m_i-1)/(m_i\lambda_i) ( m i − 1 ) / ( m i λ i ) and ( m i − 1 ) / ( m i λ i 2 ) (m_i-1)/(m_i\lambda_i^2) ( m i − 1 ) / ( m i λ i 2 ) , because ( L W i + c i I ) − 1 (L_{W_i}+c_iI)^{-1} ( L W i + c i I ) − 1 acts on the vectors in R M i \mathbb{R}^{M_i} R M i with zero sum as multiplication by 1 / λ i 1/\lambda_i 1/ λ i .
Effective resistances in several classes of graph blow-ups have been studied previously. Azimi, Bapat and Farrokhi [34 ] derived resistance formulas for blow-ups of trees in which every vertex is replaced by a copy of a fixed clique or a fixed independent set. More recently, Liu, Li, You, Hua and Chen [35 ] treated generalised blow-ups of an arbitrary base graph H H H whose modules are disjoint unions of isolated vertices and copies of a single clique K t K_t K t (with t t t common to all modules), reducing their effective resistances to those of a vertex-weighted quotient on V ( H ) V(H) V ( H ) . Because L v v † = R v / n − Kf ( G ) / n 2 L^\dagger_{vv}=R_v/n-\operatorname{Kf}(G)/n^2 L v v † = R v / n − Kf ( G ) / n 2 by (2) , pairwise resistance formulas determine the diagonal of L † L^\dagger L † in principle for those families. Proposition 5.3 accommodates cliques and independent sets of arbitrary, module-dependent sizes m i m_i m i and isolates the diagonals of both L † L^\dagger L † and ( L † ) 2 (L^\dagger)^2 ( L † ) 2 directly in the form required to test resistance-regularity.
When H H H is a tree, the system (15) can be solved by inspection: the current between two adjacent modules is determined by the total demand on one side, as in a series circuit. This gives a criterion that can be checked by hand.
Corollary 5.4. Let H H H be a tree on { 1 , … , r } \{1,\ldots,r\} { 1 , … , r } , let m 1 , … , m r ≥ 1 m_1,\ldots,m_r\ge1 m 1 , … , m r ≥ 1 , let W 1 , … , W r W_1,\ldots,W_r W 1 , … , W r be walk-regular graphs with ∣ V ( W i ) ∣ = m i |V(W_i)|=m_i ∣ V ( W i ) ∣ = m i , and let G = H [ W 1 , … , W r ] G=H[W_1,\ldots,W_r] G = H [ W 1 , … , W r ] . For each i i i put T i = 1 m i ∑ ν + c i 1 ν T_i=\frac{1}{m_i}\sum_{\nu+c_i}\frac{1}{\nu} T i = m i 1 ∑ ν + c i ν 1 as in Lemma 5.2, with c i = ∑ j ∼ i m j c_i=\sum_{j\sim i}m_j c i = ∑ j ∼ i m j , and for an edge j k jk j k of H H H and a vertex i i i of H H H let A j k ( i ) A_{jk}^{(i)} A j k ( i ) be the total size of the modules in the component of H − j k H-jk H − j k that does not contain i i i . Then for every vertex v ∈ M i v\in M_i v ∈ M i ,
L v v † = T i + 1 n 2 ∑ j k ∈ E ( H ) ( A j k ( i ) ) 2 m j m k . L^\dagger_{vv}=T_i+\frac{1}{n^2}\sum_{jk\in E(H)}\frac{\left(A_{jk}^{(i)}\right)^2}{m_jm_k}. L v v † = T i + n 2 1 j k ∈ E ( H ) ∑ m j m k ( A j k ( i ) ) 2 . Consequently G G G is resistance-regular if and only if, for every edge i j ij ij of H H H ,
T j − T i = n − 2 A i j n m i m j . (16) T_j-T_i=\frac{n-2A_{ij}}{nm_im_j}. \tag*{(16)} T j − T i = n m i m j n − 2 A ij . (16) where A i j A_{ij} A ij is the total size of the modules on the side of i i i in H − i j H-ij H − ij .
Proof. By Lemma 5.2, L v v † = T i + 1 M i ⊤ L † 1 M i / m i 2 L^\dagger_{vv}=T_i+\mathbf{1}_{M_i}^{\top}L^\dagger\mathbf{1}_{M_i}/m_i^2 L v v † = T i + 1 M i ⊤ L † 1 M i / m i 2 . Set φ = L † 1 M i \varphi=L^\dagger\mathbf{1}_{M_i} φ = L † 1 M i . By the invariance argument in the proof of Proposition 5.3 (which does not depend on the internal structure of the modules), φ \varphi φ is constant on every module M j M_j M j , and hence only edges between distinct modules contribute to the quadratic form 1 M i ⊤ L † 1 M i = φ ⊤ L φ = ∑ a b ∈ E ( G ) ( φ a − φ b ) 2 \mathbf{1}_{M_i}^{\top}L^\dagger\mathbf{1}_{M_i}=\varphi^{\top}L\varphi=\sum_{ab\in E(G)}(\varphi_a-\varphi_b)^2 1 M i ⊤ L † 1 M i = φ ⊤ L φ = ∑ ab ∈ E ( G ) ( φ a − φ b ) 2 . Let j k jk j k be an edge of H H H and S S S the set of vertices of G G G lying in modules of the component of H − j k H-jk H − j k not containing i i i . Summing the equations ( L φ ) a = − m i / n (L\varphi)_a=-m_i/n ( L φ ) a = − m i / n over a ∈ S a\in S a ∈ S , the edges inside S S S cancel and only the m j m k m_jm_k m j m k edges between M j M_j M j and M k M_k M k remain, each carrying the same potential difference; hence m j m k ∣ φ j − φ k ∣ = m i A j k ( i ) / n m_jm_k|\varphi_j-\varphi_k|=m_iA_{jk}^{(i)}/n m j m k ∣ φ j − φ k ∣ = m i A j k ( i ) / n , where φ j \varphi_j φ j denotes the value of φ \varphi φ on M j M_j M j . The energy of φ \varphi φ is therefore ∑ j k m j m k ( φ j − φ k ) 2 = ( m i 2 / n 2 ) ∑ j k ( A j k ( i ) ) 2 / ( m j m k ) \sum_{jk}m_jm_k(\varphi_j-\varphi_k)^2=(m_i^2/n^2)\sum_{jk}(A_{jk}^{(i)})^2/(m_jm_k) ∑ j k m j m k ( φ j − φ k ) 2 = ( m i 2 / n 2 ) ∑ j k ( A j k ( i ) ) 2 / ( m j m k ) , which gives the formula for L v v † L^\dagger_{vv} L v v † . If i i i and j j j are adjacent in H H H , then every edge of H H H other than i j ij ij has the same far side as seen from i i i and from j j j , while for the edge i j ij ij itself the far side has size n − A i j n-A_{ij} n − A ij as seen from i i i and A i j A_{ij} A ij as seen from j j j . Hence L v v † − L w w † = T i − T j + ( ( n − A i j ) 2 − A i j 2 ) / ( n 2 m i m j ) L^\dagger_{vv}-L^\dagger_{ww}=T_i-T_j+\big((n-A_{ij})^2-A_{ij}^2\big)/(n^2m_im_j) L v v † − L w w † = T i − T j + ( ( n − A ij ) 2 − A ij 2 ) / ( n 2 m i m j ) for v ∈ M i v\in M_i v ∈ M i and w ∈ M j w\in M_j w ∈ M j , which vanishes exactly when (16) holds. Since H H H is connected, L † L^{\dagger} L † has constant diagonal if and only if this holds for every edge.
Graphs with two consecutive degrees. A different substitution turns any example with two consecutive degrees into an infinite sequence of examples.
Proposition 5.5. Let G G G be a connected resistance-regular graph on n n n vertices whose degrees are d d d and d + 1 d+1 d + 1 , and let m ≥ 1 m \ge1 m ≥ 1 . Let G ( m ) G^{(m)} G ( m ) be the blow-up of G G G in which every vertex of degree d d d is replaced by a clique K m K_m K m and every vertex of degree d + 1 d+1 d + 1 by an independent set K ‾ m \overline{K}_m K m . Then G ( m ) G^{(m)} G ( m ) is a connected resistance-regular graph on m n mn mn vertices with degrees m ( d + 1 ) − 1 m(d+1)-1 m ( d + 1 ) − 1 and m ( d + 1 ) m(d+1) m ( d + 1 ) , and for a vertex w w w in the module of a vertex v v v of G G G ,
L w w † ( G ( m ) ) = m − 1 m 2 ( d + 1 ) + L v v † ( G ) m 2 , ( ( L † ) 2 ) w w ( G ( m ) ) = m − 1 m 3 ( d + 1 ) 2 + ( ( L † ) 2 ) v v ( G ) m 3 . L^{\dagger}_{ww}(G^{(m)}) = \frac{m-1}{m^2(d+1)} + \frac{L^{\dagger}_{vv}(G)}{m^2}, \qquad\left((L^{\dagger})^2\right)_{ww}(G^{(m)}) = \frac{m-1}{m^3(d+1)^2} + \frac{\left((L^{\dagger})^2\right)_{vv}(G)}{m^3}. L w w † ( G ( m ) ) = m 2 ( d + 1 ) m − 1 + m 2 L v v † ( G ) , ( ( L † ) 2 ) w w ( G ( m ) ) = m 3 ( d + 1 ) 2 m − 1 + m 3 ( ( L † ) 2 ) v v ( G ) .
Proof. All modules have size m m m . A module replacing a vertex v v v has c v = m d v c_v = md_v c v = m d v outside neighbours, so λ v = m d + m = m ( d + 1 ) \lambda_v = md + m = m(d+1) λ v = m d + m = m ( d + 1 ) if d v = d d_v = d d v = d (clique) and λ v = m ( d + 1 ) \lambda_v = m(d+1) λ v = m ( d + 1 ) if d v = d + 1 d_v = d+1 d v = d + 1 (independent set); thus λ v = m ( d + 1 ) \lambda_v = m(d+1) λ v = m ( d + 1 ) for every v v v . With all m j = m m_j = m m j = m , the system (15) for the module of v v v reads m ( L G y ) u = δ u v − 1 / n m(L_Gy)_u = \delta_{uv} - 1/n m ( L G y ) u = δ uv − 1/ n for u ∈ V ( G ) u \in V(G) u ∈ V ( G ) , together with ∑ u y u = 0 \sum_u y_u = 0 ∑ u y u = 0 , so its solution is y = 1 m L † ( G ) e v y = \frac{1}{m}L^{\dagger}(G)e_v y = m 1 L † ( G ) e v . Hence y v = L v v † ( G ) / m y_v = L^{\dagger}_{vv}(G)/m y v = L v v † ( G ) / m and ∑ u m y u 2 = ( ( L † ) 2 ) v v ( G ) / m \sum_u m y_u^2 = ((L^{\dagger})^2)_{vv}(G)/m ∑ u m y u 2 = (( L † ) 2 ) v v ( G ) / m , and Proposition 5.3 gives the two formulas; the first is constant because G G G is resistance-regular. The degrees are ( m − 1 ) + m d (m-1)+md ( m − 1 ) + m d and m ( d + 1 ) m(d+1) m ( d + 1 ) .
Applied to the graphs of Table 2 , Proposition 5.5 produces from each of them an infinite sequence of non-regular resistance-regular graphs with two consecutive degrees, and graph 12 of that table is in fact F ( 4 ) ( 2 ) \mathcal{F}(4)^{(2)} F ( 4 ) ( 2 ) . Several of the other graphs in Table 2 are blow-ups as well; for instance, graph 2 is the blow-up C 9 [ K 4 , K ‾ 2 , K ‾ 2 , K 4 , K ‾ 2 , K ‾ 2 , K 4 , K ‾ 2 , K ‾ 2 ] C_9[K_4,\overline{K}_2,\overline{K}_2,K_4,\overline{K}_2,\overline{K}_2,K_4,\overline{K}_2,\overline{K}_2] C 9 [ K 4 , K 2 , K 2 , K 4 , K 2 , K 2 , K 4 , K 2 , K 2 ] of the 9-cycle. By contrast, replacing every vertex of F ( 4 ) \mathcal{F}(4) F ( 4 ) by modules of a single type, as in the lexicographic products F ( 4 ) [ K 2 ] \mathcal{F}(4)[K_2] F ( 4 ) [ K 2 ] and F ( 4 ) [ K ‾ 2 ] \mathcal{F}(4)[\overline{K}_2] F ( 4 ) [ K 2 ] , destroys resistance-regularity, and other standard graph products do not produce new examples either.
Remark 5.6 (graph products). For G = F ( 4 ) G = \mathcal{F}(4) G = F ( 4 ) , none of the Cartesian products G □ K 2 G \mathbin{\square} K_2 G □ K 2 , G □ C 4 G \mathbin{\square} C_4 G □ C 4 , G □ K 4 G \mathbin{\square} K_4 G □ K 4 , G □ G G \mathbin{\square} G G □ G and G □ F ( 6 ) G \mathbin{\square} \mathcal{F}(6) G □ F ( 6 ) , the tensor product G × K 2 G \times K_2 G × K 2 , the lexicographic products G [ K 2 ] = G ⊠ K 2 G[K_2] = G \boxtimes K_2 G [ K 2 ] = G ⊠ K 2 and G [ K ‾ 2 ] G[\overline{K}_2] G [ K 2 ] , the complement and the line graph of G G G is resistance-regular, and joins are excluded in general by Theorem A(iii). For a Cartesian product G □ H G \mathbin{\square} H G □ H , the diagonal entry of L † L^{\dagger} L † at ( v , w ) (v,w) ( v , w ) is ∑ ( i , j ) ≠ ( 0 , 0 ) e i ( v ) f j ( w ) / ( μ i + ν j ) \sum_{(i,j)\ne(0,0)} e_i(v)f_j(w)/(\mu_i+\nu_j) ∑ ( i , j ) = ( 0 , 0 ) e i ( v ) f j ( w ) / ( μ i + ν j ) , where ( e i ( v ) ) (e_i(v)) ( e i ( v )) and ( f j ( w ) ) (f_j(w)) ( f j ( w )) are the local spectral measures of G G G and H H H including the eigenvalue μ 0 = ν 0 = 0 \mu_0=\nu_0=0 μ 0 = ν 0 = 0 ; resistance-regularity of G G G controls the resolvent ν ↦ ∑ i ≥ 1 e i ( v ) / ( μ i + ν ) \nu\mapsto\sum_{i\ge1} e_i(v)/(\mu_i+\nu) ν ↦ ∑ i ≥ 1 e i ( v ) / ( μ i + ν ) only at ν = 0 \nu=0 ν = 0 .
How far from regular
Every non-regular resistance-regular graph constructed in § 4 had two consecutive vertex degrees d d d and d + 1 d+1 d + 1 . Using the module machinery of § 5 , we now show that neither the degree difference Δ − δ \Delta-\delta Δ − δ nor the number of distinct degrees is limited to the patterns seen in Table 2 . We first construct a family of blown-up hexagons C 6 ( t , t 2 ) C_6(t,t^2) C 6 ( t , t 2 ) whose two degrees differ by ( 4 n + 1 − 5 ) / 4 (\sqrt{4n+1}-5)/4 ( 4 n + 1 − 5 ) /4 and path blow-ups with three and four distinct degrees, and then establish the general upper bounds on Δ − δ \Delta-\delta Δ − δ stated in Theorem C(iii). Throughout this section, Δ \Delta Δ and δ \delta δ denote the maximum and minimum degrees of G G G , and R R R also denotes the common resistance degree R v R_v R v when G G G is resistance-regular.
The blown-up hexagon
For integers x , y ≥ 1 x,y \ge1 x , y ≥ 1 , let C 6 ( x , y ) C_6(x,y) C 6 ( x , y ) be the blow-up of the cycle C 6 C_6 C 6 on { 0 , 1 , … , 5 } \{0,1,\ldots,5\} { 0 , 1 , … , 5 } in which M 0 M_0 M 0 and M 3 M_3 M 3 are independent sets of size x x x and M 1 , M 2 , M 4 , M 5 M_1,M_2,M_4,M_5 M 1 , M 2 , M 4 , M 5 are cliques of size y y y , consecutive modules M i M_i M i and M i + 1 M_{i+1} M i + 1 (indices modulo 6) are completely joined, as in Figure 3 . The graph has n = 2 x + 4 y n = 2x + 4y n = 2 x + 4 y vertices; a vertex of M 0 M_0 M 0 or M 3 M_3 M 3 has degree 2 y 2y 2 y , and a vertex of a clique module has degree ( y − 1 ) + x + y = x + 2 y − 1 (y - 1) + x + y = x + 2y - 1 ( y − 1 ) + x + y = x + 2 y − 1 .
Figure 3. The graph C 6 ( x , y ) C_6(x,y) C 6 ( x , y ) . Shaded modules are independent sets of size x x x , white modules are cliques of size y y y , and double lines indicate complete joins. By Lemma 6.1 , the graph is resistance-regular exactly when y = x 2 y=x^2 y = x 2 .
Lemma 6.1. For all integers x , y ≥ 1 x,y \ge1 x , y ≥ 1 , a vertex v v v of an independent module and a vertex w w w of a clique module of C 6 ( x , y ) C_6(x,y) C 6 ( x , y ) satisfy
L v v † = 4 x 2 y + x 2 + 16 x y 2 + 2 x y + 16 y 3 − 4 y 2 8 y 2 ( x + 2 y ) 2 , L^\dagger_{vv} = \frac{4x^2y + x^2 + 16xy^2 + 2xy + 16y^3 - 4y^2}{8y^2(x+2y)^2}, L v v † = 8 y 2 ( x + 2 y ) 2 4 x 2 y + x 2 + 16 x y 2 + 2 x y + 16 y 3 − 4 y 2 , L v w † = x 3 + 8 x 2 y 2 + 2 x 2 y + 16 x y 3 + 8 y 3 8 x y 2 ( x + 2 y ) 2 , L^\dagger_{vw} = \frac{x^3 + 8x^2y^2 + 2x^2y + 16xy^3 + 8y^3}{8xy^2(x+2y)^2}, L v w † = 8 x y 2 ( x + 2 y ) 2 x 3 + 8 x 2 y 2 + 2 x 2 y + 16 x y 3 + 8 y 3 , and therefore
L v v † − L w w † = x 2 − y 2 x y ( x + 2 y ) . L^\dagger_{vv} - L^\dagger_{ww} = \frac{x^2-y}{2xy(x+2y)}. L v v † − L w w † = 2 x y ( x + 2 y ) x 2 − y . In particular, C 6 ( x , y ) C_6(x,y) C 6 ( x , y ) is resistance-regular if and only if y = x 2 y=x^2 y = x 2 .
Proof. The reflection of C 6 C_6 C 6 fixing 0 and 3 and the reflection exchanging 0 with 3 and 1 with 2 preserve the types of the modules, and together with the permutations inside the modules they generate a group of automorphisms that is transitive on M 0 ∪ M 3 M_0 \cup M_3 M 0 ∪ M 3 and on the union of the four clique modules. It therefore suffices to take v ∈ M 0 v \in M_0 v ∈ M 0 and w ∈ M 1 w \in M_1 w ∈ M 1 . Here λ 0 = 2 y \lambda_0 = 2y λ 0 = 2 y and λ 1 = x + 2 y \lambda_1 = x+2y λ 1 = x + 2 y . Solving (15) for i = 0 i=0 i = 0 and i = 1 i=1 i = 1 gives, with D 0 = 8 y 2 ( x + 2 y ) 2 D_0 = 8y^2(x+2y)^2 D 0 = 8 y 2 ( x + 2 y ) 2 and D 1 = 8 x y ( x + 2 y ) 2 D_1 = 8xy(x+2y)^2 D 1 = 8 x y ( x + 2 y ) 2 ,
Table 6.
as one checks by substituting into the six equations of (15) . By Proposition 5.3 ,
L v v † = x − 1 2 x y + y 0 ( 0 ) x = 4 x 2 y + x 2 + 16 x y 2 + 2 x y + 16 y 3 − 4 y 2 8 y 2 ( x + 2 y ) 2 , L^\dagger_{vv} = \frac{x-1}{2xy} + \frac{y_0^{(0)}}{x} = \frac{4x^2y+x^2+16xy^2+2xy+16y^3-4y^2}{8y^2(x+2y)^2}, L v v † = 2 x y x − 1 + x y 0 ( 0 ) = 8 y 2 ( x + 2 y ) 2 4 x 2 y + x 2 + 16 x y 2 + 2 x y + 16 y 3 − 4 y 2 ,
L w w † = y − 1 y ( x + 2 y ) + y 1 ( 1 ) y = x 3 + 8 x 2 y 2 + 2 x 2 y + 16 x y 3 + 8 y 3 8 x y 2 ( x + 2 y ) 2 , L^\dagger_{ww} = \frac{y-1}{y(x+2y)} + \frac{y_1^{(1)}}{y} = \frac{x^3+8x^2y^2+2x^2y+16xy^3+8y^3}{8xy^2(x+2y)^2}, L w w † = y ( x + 2 y ) y − 1 + y y 1 ( 1 ) = 8 x y 2 ( x + 2 y ) 2 x 3 + 8 x 2 y 2 + 2 x 2 y + 16 x y 3 + 8 y 3 ,
and subtracting gives the stated difference. All vertices of the independent modules have the same value of L v v † L^\dagger_{vv} L v v † , and so do all vertices of the clique modules, which proves the last statement.
Blow-ups of paths
All examples so far have exactly two distinct degrees. Corollary 5.4 makes it easy to look for blow-ups of paths with more degrees, and the smallest examples we found are the following. For walk-regular graphs W 1 , … , W r W_1,\ldots,W_r W 1 , … , W r write P r [ W 1 , … , W r ] P_r[W_1,\ldots,W_r] P r [ W 1 , … , W r ] for the blow-up of the path 1 − 2 − ⋯ − r 1-2-\cdots-r 1 − 2 − ⋯ − r .
Lemma 6.2. The graph
Γ 40 = P 8 [ K 9 , K 6 ‾ , K 3 ‾ , K 2 ‾ , K 2 ‾ , K 3 , K 6 ‾ , K 9 ] \Gamma_{40}=P_8[K_9,\overline{K_6},\overline{K_3},\overline{K_2},\overline{K_2},K_3,\overline{K_6},K_9] Γ 40 = P 8 [ K 9 , K 6 , K 3 , K 2 , K 2 , K 3 , K 6 , K 9 ] is a connected resistance-regular graph on 40 vertices with exactly four distinct degrees, 5, 8, 12, 14, carried by 4, 6, 12, 18 vertices respectively, and L v v † = 99 / 400 L^{\dagger}_{vv}=99/400 L v v † = 99/400 . The graph
Γ 126 = P 10 [ K 33 , K 9 ‾ , K 3 ‾ , K 3 , 3 , 3 , K 9 ‾ , K 9 ‾ , K 3 , 3 , 3 , K 3 ‾ , K 9 ‾ , K 33 ] \Gamma_{126}=P_{10}[K_{33},\overline{K_9},\overline{K_3},K_{3,3,3},\overline{K_9},\overline{K_9},K_{3,3,3},\overline{K_3},\overline{K_9},K_{33}] Γ 126 = P 10 [ K 33 , K 9 , K 3 , K 3 , 3 , 3 , K 9 , K 9 , K 3 , 3 , 3 , K 3 , K 9 , K 33 ] is a connected resistance-regular graph on 126 vertices with exactly three distinct degrees, 18, 36, 41, carried by 42, 18, 66 vertices respectively, and L v v † = 1193 / 15876 L^{\dagger}_{vv}=1193/15876 L v v † = 1193/15876 .
Proof. Both blow-ups are symmetric under the reversal of the path, so it suffices to check (16) for the edges in the first half of the path, the edge in the middle being balanced by symmetry. For Γ 40 \Gamma_{40} Γ 40 the modules M 1 , … , M 4 M_1,\ldots,M_4 M 1 , … , M 4 have c i = 6 , 12 , 8 , 5 c_i=6,12,8,5 c i = 6 , 12 , 8 , 5 and T i = 8 135 , 5 72 , 1 12 , 1 10 T_i=\frac{8}{135},\frac{5}{72},\frac{1}{12},\frac{1}{10} T i = 135 8 , 72 5 , 12 1 , 10 1 , and for the edges { 1 , 2 } , { 2 , 3 } , { 3 , 4 } \{1,2\},\{2,3\},\{3,4\} { 1 , 2 } , { 2 , 3 } , { 3 , 4 } we have A i j = 9 , 15 , 18 A_{ij}=9,15,18 A ij = 9 , 15 , 18 , so that
40 − 18 40 ⋅ 9 ⋅ 6 = 11 1080 = T 2 − T 1 , 40 − 30 40 ⋅ 6 ⋅ 3 = 1 72 = T 3 − T 2 , 40 − 36 40 ⋅ 3 ⋅ 2 = 1 60 = T 4 − T 3 . \frac{40-18}{40\cdot9\cdot6}=\frac{11}{1080}=T_2-T_1,\qquad\frac{40-30}{40\cdot6\cdot3}=\frac{1}{72}=T_3-T_2,\qquad\frac{40-36}{40\cdot3\cdot2}=\frac{1}{60}=T_4-T_3. 40 ⋅ 9 ⋅ 6 40 − 18 = 1080 11 = T 2 − T 1 , 40 ⋅ 6 ⋅ 3 40 − 30 = 72 1 = T 3 − T 2 , 40 ⋅ 3 ⋅ 2 40 − 36 = 60 1 = T 4 − T 3 .
For Γ 126 \Gamma_{126} Γ 126 , the complete tripartite graph K 3 , 3 , 3 K_{3,3,3} K 3 , 3 , 3 is walk-regular with nonzero Laplacian eigenvalues 6 (six times) and 9 (twice). The modules M 1 , … , M 5 M_1,\ldots,M_5 M 1 , … , M 5 have c i = 9 , 36 , 18 , 12 , 18 c_i=9,36,18,12,18 c i = 9 , 36 , 18 , 12 , 18 and
T 1 = 32 33 ⋅ 42 = 16 693 , T 2 = 8 9 ⋅ 36 = 2 81 , T 3 = 2 3 ⋅ 18 = 1 27 , T_1=\frac{32}{33\cdot42}=\frac{16}{693},\qquad T_2=\frac{8}{9\cdot36}=\frac{2}{81},\qquad T_3=\frac{2}{3\cdot18}=\frac{1}{27}, T 1 = 33 ⋅ 42 32 = 693 16 , T 2 = 9 ⋅ 36 8 = 81 2 , T 3 = 3 ⋅ 18 2 = 27 1 ,
T 4 = 1 9 ( 6 18 + 2 21 ) = 1 21 , T 5 = 8 9 ⋅ 18 = 4 81 , T_4=\frac{1}{9}\left(\frac{6}{18}+\frac{2}{21}\right)=\frac{1}{21},\qquad T_5=\frac{8}{9\cdot18}=\frac{4}{81}, T 4 = 9 1 ( 18 6 + 21 2 ) = 21 1 , T 5 = 9 ⋅ 18 8 = 81 4 ,
and for the edges { 1 , 2 } , … , { 4 , 5 } \{1,2\},\ldots,\{4,5\} { 1 , 2 } , … , { 4 , 5 } we have A i j = 33 , 42 , 45 , 54 A_{ij}=33,42,45,54 A ij = 33 , 42 , 45 , 54 , so that
60 126 ⋅ 33 ⋅ 9 = 10 6237 = T 2 − T 1 , 42 126 ⋅ 27 = 1 81 = T 3 − T 2 , \frac{60}{126\cdot33\cdot9}=\frac{10}{6237}=T_2-T_1,\qquad\frac{42}{126\cdot27}=\frac{1}{81}=T_3-T_2, 126 ⋅ 33 ⋅ 9 60 = 6237 10 = T 2 − T 1 , 126 ⋅ 27 42 = 81 1 = T 3 − T 2 ,
36 126 ⋅ 27 = 2 189 = T 4 − T 3 , 18 126 ⋅ 81 = 1 567 = T 5 − T 4 . \frac{36}{126\cdot27}=\frac{2}{189}=T_4-T_3,\qquad\frac{18}{126\cdot81}=\frac{1}{567}=T_5-T_4. 126 ⋅ 27 36 = 189 2 = T 4 − T 3 , 126 ⋅ 81 18 = 567 1 = T 5 − T 4 .
By Corollary 5.4, both graphs are resistance-regular, and the stated values of L v v † L^{\dagger}_{vv} L v v † follow from the formula in Corollary 5.4. The degrees of the vertices in the first half of Γ 40 \Gamma_{40} Γ 40 are 8 + 6 = 14 8+6=14 8 + 6 = 14 , 9 + 3 = 12 9+3=12 9 + 3 = 12 , 6 + 2 = 8 6+2=8 6 + 2 = 8 and 3 + 2 = 5 3+2=5 3 + 2 = 5 ; in Γ 126 \Gamma_{126} Γ 126 they are 32 + 9 = 41 32+9=41 32 + 9 = 41 , 33 + 3 = 36 33+3=36 33 + 3 = 36 , 9 + 9 = 18 9+9=18 9 + 9 = 18 , 6 + 3 + 9 = 18 6+3+9=18 6 + 3 + 9 = 18 and 9 + 9 = 18 9+9=18 9 + 9 = 18 .
Proof of Theorem C
Proof of Theorem C. (i) Let t ≥ 2 t\ge2 t ≥ 2 and G = C 6 ( t , t 2 ) G=C_6(t,t^2) G = C 6 ( t , t 2 ) . By Lemma 6.1 with x = t x=t x = t and y = t 2 = x 2 y=t^2=x^2 y = t 2 = x 2 , the graph G G G is resistance-regular, and its common diagonal entry simplifies to
L v v † = 16 t 4 + 16 t 3 + 2 t + 1 8 t 4 ( 2 t + 1 ) 2 . L^{\dagger}_{vv}=\frac{16t^4+16t^3+2t+1}{8t^4(2t+1)^2}. L v v † = 8 t 4 ( 2 t + 1 ) 2 16 t 4 + 16 t 3 + 2 t + 1 .
The graph G G G is connected and has n = 2 x + 4 y = 4 t 2 + 2 t n=2x+4y=4t^2+2t n = 2 x + 4 y = 4 t 2 + 2 t vertices. The 2 t 2t 2 t vertices of the independent modules have degree 2 y = 2 t 2 2y=2t^2 2 y = 2 t 2 , and the 4 t 2 4t^2 4 t 2 vertices of the clique modules have degree x + 2 y − 1 = 2 t 2 + t − 1 x + 2y - 1 = 2t^{2} + t - 1 x + 2 y − 1 = 2 t 2 + t − 1 . These degrees differ by t − 1 ≥ 1 t - 1 \ge1 t − 1 ≥ 1 , and since 4 n + 1 = ( 4 t + 1 ) 2 4n + 1 = (4t + 1)^{2} 4 n + 1 = ( 4 t + 1 ) 2 , we have t − 1 = ( 4 n + 1 − 5 ) / 4 t - 1 = (\sqrt{4n + 1} - 5)/4 t − 1 = ( 4 n + 1 − 5 ) /4 .
(ii) By Lemma 6.2, Γ 126 \Gamma_{126} Γ 126 has exactly three distinct degrees and Γ 40 \Gamma_{40} Γ 40 has exactly four.
(iii) Let G G G be a connected resistance-regular graph on n ≥ 3 n \ge3 n ≥ 3 vertices. Let u u u be a vertex of degree Δ \Delta Δ , put D = Δ + 1 D = \Delta+ 1 D = Δ + 1 , and let F = V ∖ ( { u } ∪ N ( u ) ) F = V \setminus(\{u\} \cup N(u)) F = V ∖ ({ u } ∪ N ( u )) , so that ∣ F ∣ = n − D |F| = n - D ∣ F ∣ = n − D . By Theorem 2.4 (iii),
R = R u = ( 2 − 2 n ) + ∑ w ∈ F r u w . R = R_u = \left(2 - \frac{2}{n}\right) + \sum_{w \in F} r_{uw}. R = R u = ( 2 − n 2 ) + w ∈ F ∑ r u w .
For w ∈ F w \in F w ∈ F and z ∈ { u } ∪ N ( u ) z \in\{u\} \cup N(u) z ∈ { u } ∪ N ( u ) , the triangle inequality gives r w z ≥ r u w − r u z r_{wz} \ge r_{uw} - r_{uz} r w z ≥ r u w − r u z . Summing over the D D D vertices z z z and using Theorem 2.4 (iii) at u u u once more, we get R = R w ≥ D r u w − ( 2 − 2 / n ) R = R_w \ge D r_{uw} - (2 - 2/n) R = R w ≥ D r u w − ( 2 − 2/ n ) . Summing over w ∈ F w \in F w ∈ F gives ( n − D ) ( R + 2 − 2 / n ) ≥ D ( R − 2 + 2 / n ) (n-D)(R+2-2/n) \ge D(R-2+2/n) ( n − D ) ( R + 2 − 2/ n ) ≥ D ( R − 2 + 2/ n ) , that is, ( 2 D − n ) R ≤ 2 ( n − 1 ) (2D-n)R \le2(n-1) ( 2 D − n ) R ≤ 2 ( n − 1 ) . On the other hand, at a vertex w 0 w_0 w 0 of degree δ \delta δ , the third inequality of Lemma 2.7 gives r w 0 z ≥ 1 δ + 1 + 1 D r_{w_0z} \ge\frac{1}{\delta+1} + \frac{1}{D} r w 0 z ≥ δ + 1 1 + D 1 for every z ≠ w 0 z \ne w_0 z = w 0 , so R ≥ ( n − 1 ) ( 1 δ + 1 + 1 D ) R \ge(n-1)\left(\frac{1}{\delta+1}+\frac{1}{D}\right) R ≥ ( n − 1 ) ( δ + 1 1 + D 1 ) . If 2 D > n 2D > n 2 D > n , combining the two bounds gives
1 δ + 1 ≤ 2 2 D − n − 1 D = n D ( 2 D − n ) , \frac{1}{\delta+1} \le\frac{2}{2D-n} - \frac{1}{D} = \frac{n}{D(2D-n)}, δ + 1 1 ≤ 2 D − n 2 − D 1 = D ( 2 D − n ) n ,
that is, ( δ + 1 ) n ≥ ( Δ + 1 ) ( 2 Δ + 2 − n ) (\delta+1)n \ge(\Delta+1)(2\Delta+2-n) ( δ + 1 ) n ≥ ( Δ + 1 ) ( 2Δ + 2 − n ) . Then Δ − δ = D − ( δ + 1 ) ≤ D − D ( 2 D − n ) / n = 2 D ( n − D ) / n ≤ n / 2 \Delta-\delta= D-(\delta+1) \le D-D(2D-n)/n = 2D(n-D)/n \le n/2 Δ − δ = D − ( δ + 1 ) ≤ D − D ( 2 D − n ) / n = 2 D ( n − D ) / n ≤ n /2 , with equality only if D = n / 2 D=n/2 D = n /2 , which is excluded. If 2 D ≤ n 2D \le n 2 D ≤ n , then Δ − δ ≤ Δ − 1 < D ≤ n / 2 \Delta-\delta\le\Delta-1 < D \le n/2 Δ − δ ≤ Δ − 1 < D ≤ n /2 . Hence Δ − δ < n / 2 \Delta-\delta< n/2 Δ − δ < n /2 in all cases.
Now suppose that G G G has exactly two distinct degrees δ < Δ \delta< \Delta δ < Δ , and put g = Δ − δ g = \Delta-\delta g = Δ − δ . Because G G G is connected and has two degree classes, some vertex x x x of degree Δ \Delta Δ has b ≥ 1 b \ge1 b ≥ 1 neighbours of degree δ \delta δ . By Theorem 2.4 (iii) and the second inequality of Lemma 2.7,
2 − 2 n = ∑ u ∼ x r x u ≥ ∑ u ∼ x Δ + d u − 2 Δ d u − 1 . 2-\frac{2}{n} = \sum_{u \sim x} r_{xu} \ge\sum_{u \sim x} \frac{\Delta+d_u-2}{\Delta d_u-1}. 2 − n 2 = u ∼ x ∑ r xu ≥ u ∼ x ∑ Δ d u − 1 Δ + d u − 2 .
A term with d u = Δ d_u = \Delta d u = Δ equals 2 / ( Δ + 1 ) 2/(\Delta+1) 2/ ( Δ + 1 ) , and a term with d u = δ d_u = \delta d u = δ equals 2 / ( Δ + 1 ) + g ( Δ − 1 ) / ( ( Δ δ − 1 ) ( Δ + 1 ) ) 2/(\Delta+1) + g(\Delta-1)/((\Delta\delta-1)(\Delta+1)) 2/ ( Δ + 1 ) + g ( Δ − 1 ) / (( Δ δ − 1 ) ( Δ + 1 )) . Hence
b g ( Δ − 1 ) Δ δ − 1 ≤ ( Δ + 1 ) ( 2 − 2 n ) − 2 Δ = 2 ( n − 1 − Δ ) n . \frac{b g(\Delta-1)}{\Delta\delta-1} \le(\Delta+1)\left(2-\frac{2}{n}\right)-2\Delta= \frac{2(n-1-\Delta)}{n}. Δ δ − 1 b g ( Δ − 1 ) ≤ ( Δ + 1 ) ( 2 − n 2 ) − 2Δ = n 2 ( n − 1 − Δ ) .
Since ( Δ − 1 ) ( δ + 1 ) − ( Δ δ − 1 ) = Δ − δ > 0 (\Delta-1)(\delta+1)-(\Delta\delta-1)=\Delta-\delta>0 ( Δ − 1 ) ( δ + 1 ) − ( Δ δ − 1 ) = Δ − δ > 0 , we have ( Δ − 1 ) / ( Δ δ − 1 ) > 1 / ( δ + 1 ) (\Delta-1)/(\Delta\delta-1)>1/(\delta+1) ( Δ − 1 ) / ( Δ δ − 1 ) > 1/ ( δ + 1 ) , and with b ≥ 1 b \ge1 b ≥ 1 we obtain
Δ − δ < 2 ( δ + 1 ) ( n − 1 − Δ ) n . (17) \Delta-\delta< \frac{2(\delta+1)(n-1-\Delta)}{n}. \tag*{(17)} Δ − δ < n 2 ( δ + 1 ) ( n − 1 − Δ ) . (17)
Substituting Δ = δ + g \Delta=\delta+g Δ = δ + g and rearranging gives g < f ( δ + 1 ) g < f(\delta+1) g < f ( δ + 1 ) with f ( z ) = 2 z ( n − z ) / ( n + 2 z ) f(z)=2z(n-z)/(n+2z) f ( z ) = 2 z ( n − z ) / ( n + 2 z ) , and the maximum of f f f over z > 0 z>0 z > 0 is attained at z = ( 3 − 1 ) n / 2 z=(\sqrt{3}-1)n/2 z = ( 3 − 1 ) n /2 and equals ( 2 − 3 ) n (2-\sqrt{3})n ( 2 − 3 ) n .
The proof of part (iii) gives slightly more: if 2 ( Δ + 1 ) > n 2(\Delta+1)>n 2 ( Δ + 1 ) > n , then ( δ + 1 ) n ≥ ( Δ + 1 ) ( 2 Δ + 2 − n ) (\delta+1)n \ge(\Delta+1)(2\Delta+2-n) ( δ + 1 ) n ≥ ( Δ + 1 ) ( 2Δ + 2 − n ) , and with two degrees (17) holds. For Δ = n − 1 \Delta=n-1 Δ = n − 1 the first inequality gives δ = n − 1 \delta=n-1 δ = n − 1 , which recovers the fact that a resistance-regular graph with a vertex adjacent to all others is complete. For t = 1 t=1 t = 1 , C 6 ( 1 , 1 ) C_6(1,1) C 6 ( 1 , 1 ) is the 6-cycle. The graphs C 6 ( 2 , 4 ) C_6(2,4) C 6 ( 2 , 4 ) and C 6 ( 3 , 9 ) C_6(3,9) C 6 ( 3 , 9 ) have 20 and 42 vertices; the first is, as far as we know, the second smallest non-regular resistance-regular graph, after F ( 4 ) F(4) F ( 4 ) (see Table 3 ). The graph Γ 40 \Gamma_{40} Γ 40 has Δ − δ = 9 \Delta-\delta=9 Δ − δ = 9 , that is, 0.225 n 0.225n 0.225 n .
Table 3. A selection of further non-regular resistance-regular graphs; degrees are listed with the number of vertices of each degree as an exponent. The graphs on 24, 55, 60 and 192 vertices are described in Appendix § 10 , the graph on 33 vertices is given in the ancillary files, and all are available in graph6 format there.
Algebraic connectivity and the largest difference of degrees
Large differences of degrees also force the graph to have a bottleneck. Recall that the algebraic connectivity μ 1 \mu_1 μ 1 of G G G is its smallest nonzero Laplacian eigenvalue.
Proposition 6.3. Every connected resistance-regular graph on n ≥ 3 n \ge3 n ≥ 3 vertices satisfies
( Δ − δ ) ( n − 2 ) μ 1 ≤ δ ( n − Δ ) . (\Delta-\delta)(n-2)\mu_1 \le\delta(n-\Delta). ( Δ − δ ) ( n − 2 ) μ 1 ≤ δ ( n − Δ ) .
Proof. For a vertex v v v let π v = 1 d v ∑ u ∼ v e u \pi_v=\frac{1}{d_v}\sum_{u\sim v}e_u π v = d v 1 ∑ u ∼ v e u be the uniform distribution on its neighbours. Since L e v = d v ( e v − π v ) Le_v=d_v(e_v-\pi_v) L e v = d v ( e v − π v ) , we have ( e v − π v ) ⊤ L † ( e v − π v ) = e v ⊤ L L † L e v / d v 2 = 1 / d v (e_v-\pi_v)^\top L^\dagger(e_v-\pi_v)=e_v^\top LL^\dagger Le_v/d_v^2=1/d_v ( e v − π v ) ⊤ L † ( e v − π v ) = e v ⊤ L L † L e v / d v 2 = 1/ d v and e v ⊤ L † ( e v − π v ) = e v ⊤ L † L e v / d v = ( 1 − 1 / n ) / d v e_v^\top L^\dagger(e_v-\pi_v)=e_v^\top L^\dagger Le_v/d_v=(1-1/n)/d_v e v ⊤ L † ( e v − π v ) = e v ⊤ L † L e v / d v = ( 1 − 1/ n ) / d v . Expanding π v ⊤ L † π v \pi_v^\top L^\dagger\pi_v π v ⊤ L † π v with π v = e v − ( e v − π v ) \pi_v=e_v-(e_v-\pi_v) π v = e v − ( e v − π v ) gives the identity
L v v † = π v ⊤ L † π v + ( 1 − 2 n ) 1 d v . L^\dagger_{vv}=\pi_v^\top L^\dagger\pi_v+\left(1-\frac{2}{n}\right)\frac{1}{d_v}. L v v † = π v ⊤ L † π v + ( 1 − n 2 ) d v 1 .
valid in every connected graph. Let x x x have degree Δ \Delta Δ and w w w degree δ \delta δ . If G G G is resistance-regular, subtracting the identities at x x x and w w w gives π x ⊤ L † π x − π w ⊤ L † π w = ( 1 − 2 / n ) ( 1 / δ − 1 / Δ ) \pi_x^\top L^\dagger\pi_x-\pi_w^\top L^\dagger\pi_w=(1-2/n)(1/\delta-1/\Delta) π x ⊤ L † π x − π w ⊤ L † π w = ( 1 − 2/ n ) ( 1/ δ − 1/Δ ) . Since L † 1 = 0 L^\dagger\mathbf{1}=0 L † 1 = 0 and π x − 1 / n ⊥ 1 \pi_x-1/n\perp\mathbf{1} π x − 1/ n ⊥ 1 , we have π x ⊤ L † π x = ( π x − 1 / n ) ⊤ L † ( π x − 1 / n ) ≤ ∥ π x − 1 / n ∥ 2 / μ 1 = ( 1 / Δ − 1 / n ) / μ 1 \pi_x^\top L^\dagger\pi_x=(\pi_x-1/n)^\top L^\dagger(\pi_x-1/n)\leq\|\pi_x-1/n\|^2/\mu_1=(1/\Delta-1/n)/\mu_1 π x ⊤ L † π x = ( π x − 1/ n ) ⊤ L † ( π x − 1/ n ) ≤ ∥ π x − 1/ n ∥ 2 / μ 1 = ( 1/Δ − 1/ n ) / μ 1 , while π w ⊤ L † π w ≥ 0 \pi_w^\top L^\dagger\pi_w\geq0 π w ⊤ L † π w ≥ 0 . Therefore ( 1 − 2 / n ) ( Δ − δ ) / ( δ Δ ) ≤ ( n − Δ ) / ( n Δ μ 1 ) (1-2/n)(\Delta-\delta)/(\delta\Delta)\leq(n-\Delta)/(n\Delta\mu_1) ( 1 − 2/ n ) ( Δ − δ ) / ( δ Δ ) ≤ ( n − Δ ) / ( n Δ μ 1 ) , which rearranges to the claim. □ \square □
Write g ( n ) g(n) g ( n ) for the largest value of Δ − δ \Delta-\delta Δ − δ over all connected resistance-regular graphs on n n n vertices. Theorem C gives
4 n + 1 − 5 4 ≤ g ( n ) < n 2 for n = 4 t 2 + 2 t , t ≥ 2 , \frac{\sqrt{4n+1}-5}{4}\leq g(n)<\frac{n}{2}\qquad\text{for }n=4t^2+2t,\ t\geq2, 4 4 n + 1 − 5 ≤ g ( n ) < 2 n for n = 4 t 2 + 2 t , t ≥ 2 ,
and by Proposition 6.3, resistance-regular graphs whose degrees differ substantially must have small algebraic connectivity. The order of growth of g ( n ) g(n) g ( n ) is open; see § 8 .
Further examples
Additional examples with three distinct degrees can be obtained by blowing up other trees and block graphs, the smallest of which after Γ 126 \Gamma_{126} Γ 126 has 192 vertices (described in Appendix § 10 ). Searching over blow-ups of all connected base graphs on at most seven vertices with walk-regular modules yielded no example with three or more degrees on fewer than 40 vertices, and an exhaustive check of all 3.1 × 10 8 3.1\times10^8 3.1 × 1 0 8 connected tri-circulants over Z k \mathbb{Z}_k Z k for k ≤ 7 k\leq7 k ≤ 7 (graphs admitting a three-orbit semiregular cyclic automorphism group) produced no non-regular resistance-regular graph at all. Whether the number of distinct vertex degrees in a resistance-regular graph can be arbitrarily large remains open.
The constructions of § 5 and § 6 , together with searches over module blow-ups and over graphs with a two-orbit abelian group of automorphisms, produced many further examples. We collected 138 pairwise non-isomorphic non-regular resistance-regular graphs on at most 300 vertices, among them examples of odd order, each verified in exact rational arithmetic; they are listed in the ancillary files. Table 3 shows a selection: the smallest examples we know with degree differences 2, 3 and 4, the two smallest examples of odd order, and the graphs with three and four distinct degrees.
Resistance rows and the degree
Our resistance-regular graphs show that the sum R v R_v R v of the multiset { { r v u : u ∈ V } } \{\{r_{vu}: u \in V\}\} {{ r v u : u ∈ V }} does not determine d v d_v d v . Even the entire multiset { { r v u : u ∈ V } } \{\{r_{vu}: u \in V\}\} {{ r v u : u ∈ V }} at a single vertex v v v does not determine d v d_v d v , as happens already on ten vertices.
Proposition 7.1. Up to isomorphism, there are exactly two connected graphs on at most ten vertices that contain a pair of vertices x , y x,y x , y of different degrees with { { r x u : u ∈ V } } = { { r y u : u ∈ V } } \{\{r_{xu}: u \in V\}\} = \{\{r_{yu}: u \in V\}\} {{ r xu : u ∈ V }} = {{ r y u : u ∈ V }} . Both have ten vertices:
(a) K 2 , 3 K_{2,3} K 2 , 3 with one vertex x x x of the 3-element part joined to a new vertex y y y that is additionally adjacent to two pendant vertices and the two vertices of a triangle; here d x = 3 d_x=3 d x = 3 , d y = 5 d_y=5 d y = 5 , and both multisets of nonzero resistances equal { { 2 3 , 2 3 , 1 , 1 , 1 , 5 3 , 5 3 , 2 , 2 } } \{\{\frac{2}{3},\frac{2}{3},1,1,1,\frac{5}{3},\frac{5}{3},2,2\}\} {{ 3 2 , 3 2 , 1 , 1 , 1 , 3 5 , 3 5 , 2 , 2 }} ;
(b) K 2 , 3 K_{2,3} K 2 , 3 with one vertex x x x of the 2-element part joined to the central vertex y y y of a bowtie (two triangles sharing y y y ); here d x = 4 d_x=4 d x = 4 , d y = 5 d_y=5 d y = 5 , and both multisets of nonzero resistances equal { { 2 3 , 2 3 , 2 3 , 2 3 , 1 , 5 3 , 5 3 , 5 3 , 5 3 } } \{\{\frac{2}{3},\frac{2}{3},\frac{2}{3},\frac{2}{3},1,\frac{5}{3},\frac{5}{3},\frac{5}{3},\frac{5}{3}\}\} {{ 3 2 , 3 2 , 3 2 , 3 2 , 1 , 3 5 , 3 5 , 3 5 , 3 5 }} .
In both graphs, the second round of resistance-based colour refinement separates x x x from y y y , and the stable colouring coincides with the automorphism orbit partition.
Proof. We generated all 11 989 762 connected graphs on n ≤ 10 n \le10 n ≤ 10 vertices using geng, computed their effective resistances exactly as in § 3.2 (as the fractions τ r u v / τ \tau r_{uv}/\tau τ r uv / τ with integer numerators), and compared the sorted rows of R R R within each graph; every candidate pair was verified again in exact rational arithmetic. For n ≤ 9 n \le9 n ≤ 9 , every pair of vertices with identical resistance multisets has the same degree, whereas for n = 10 n=10 n = 10 only the two graphs in (a) and (b) contain a pair of vertices of unequal degree with the same resistance multiset. □
Although two individual vertices of different degrees can share the same resistance multiset, requiring every vertex of G G G to have the same resistance multiset, so that even the stable resistance-based Weisfeiler–Leman colouring cannot distinguish any two vertices, is much more restrictive.
Conjecture 7.2. Let G G G be a connected graph in which the multiset { { r v u : u ∈ V } } \{\{r_{vu}: u \in V\}\} {{ r v u : u ∈ V }} is the same for every vertex v ∈ V v \in V v ∈ V . Then G G G is regular.
The hypothesis of Conjecture 7.2 means that all rows of the resistance matrix R R R are permutations of one another. Any such graph is automatically resistance-regular, and in a resistance-regular graph the second resistance moment satisfies
∑ u ∈ V r v u 2 = n ( L v v † ) 2 + 2 L v v † tr L † + ∑ u ∈ V ( L u u † ) 2 + 4 ( ( L † ) 2 ) v v . (18) \sum_{u\in V} r_{vu}^{2}=n(L^{\dagger}_{vv})^{2}+2L^{\dagger}_{vv}\operatorname{tr}L^{\dagger}+\sum_{u\in V}(L^{\dagger}_{uu})^{2}+4((L^{\dagger})^{2})_{vv}. \tag*{(18)} u ∈ V ∑ r v u 2 = n ( L v v † ) 2 + 2 L v v † tr L † + u ∈ V ∑ ( L uu † ) 2 + 4 (( L † ) 2 ) v v . (18)
If all rows of R R R are permutations of one another, the left-hand side of (18) does not depend on v v v , and hence neither does ( ( L † ) 2 ) v v ((L^{\dagger})^{2})_{vv} (( L † ) 2 ) v v . Consequently, by Theorem A(i), Conjecture 7.2 holds whenever L L L has m ≤ 3 m \le3 m ≤ 3 distinct nonzero eigenvalues (and the second moment rules out all sixteen graphs of Table 2 ; see § 7.1 ). Using the Dirichlet bounds of Lemma 2.7 and the following maximum principle, we now prove that any connected graph whose resistance matrix has rows that are permutations of one another can have at most two consecutive degrees.
Lemma 7.3 (nearest vertices are neighbours). Let G G G be a connected resistance-regular graph and let v ∈ V v \in V v ∈ V . Every vertex u ≠ v u \ne v u = v that minimises r v u r_{vu} r v u is adjacent to v v v . Proof. Because L u u † L^\dagger_{uu} L uu † is constant across u ∈ V u \in V u ∈ V , formula (1) shows that r v u r_{vu} r v u is minimised over u ≠ v u \ne v u = v precisely when φ ( u ) = L u v † \varphi(u)=L^\dagger_{uv} φ ( u ) = L uv † is maximised over u ≠ v u \ne v u = v , where φ = L † e v \varphi=L^\dagger e_v φ = L † e v . For any vertex w ≠ v w \ne v w = v , the Laplacian equation ( L φ ) w = − 1 / n (L\varphi)_w=-1/n ( L φ ) w = − 1/ n can be written as
φ ( w ) = 1 d w ∑ u ∼ w φ ( u ) − 1 n d w . \varphi(w)=\frac{1}{d_w}\sum_{u\sim w}\varphi(u)-\frac{1}{nd_w}. φ ( w ) = d w 1 u ∼ w ∑ φ ( u ) − n d w 1 .
so φ ( w ) \varphi(w) φ ( w ) is strictly smaller than the maximum of φ \varphi φ over the neighbours of w w w . If a vertex u ∗ ∈ V ∖ { v } u^* \in V \setminus\{v\} u ∗ ∈ V ∖ { v } maximising φ \varphi φ on V ∖ { v } V \setminus\{v\} V ∖ { v } were not adjacent to v v v , then all neighbours of u ∗ u^* u ∗ would lie in V ∖ { v } V \setminus\{v\} V ∖ { v } and at least one of them would have a strictly larger value of φ \varphi φ , contradicting the choice of u ∗ u^* u ∗ . □
Proposition 7.4. Let G G G be a connected graph on n n n vertices in which all rows of the resistance matrix R R R are permutations of one another, and let Δ \Delta Δ and δ \delta δ be the maximum and minimum degrees of G G G . Then Δ − δ ≤ 1 \Delta-\delta\le1 Δ − δ ≤ 1 . Moreover, if G G G is not regular, so that its vertex degrees are k k k and k + 1 k+1 k + 1 for some k ≥ 2 k\ge2 k ≥ 2 , then n ≥ 2 k + 5 n\ge2k+5 n ≥ 2 k + 5 when k ≥ 3 k\ge3 k ≥ 3 , and n ≥ 10 n\ge10 n ≥ 10 when k = 2 k=2 k = 2 .
Proof. Because the rows of R R R are permutations of one another, G G G is resistance-regular and the minimum positive entry ρ = min u ≠ v r v u \rho=\min_{u\ne v}r_{vu} ρ = min u = v r v u in row v v v does not depend on v v v . Choose a vertex v v v of maximum degree Δ \Delta Δ . By Theorem 2.4 (iii), the Δ \Delta Δ edge resistances incident to v v v sum to 2 − 2 / n 2-2/n 2 − 2/ n , so their minimum satisfies
ρ ≤ 2 − 2 / n Δ < 2 Δ . \rho\le\frac{2-2/n}{\Delta}<\frac{2}{\Delta}. ρ ≤ Δ 2 − 2/ n < Δ 2 .
Now let w ∈ V w\in V w ∈ V be any vertex, and choose u ≠ w u\ne w u = w with r w u = ρ r_{wu}=\rho r w u = ρ . By the third inequality of Lemma 2.7 , ρ ≥ 1 d w + 1 + 1 d u + 1 ≥ 1 d w + 1 + 1 Δ + 1 \rho\ge\frac{1}{d_w+1}+\frac{1}{d_u+1}\ge\frac{1}{d_w+1}+\frac{1}{\Delta+1} ρ ≥ d w + 1 1 + d u + 1 1 ≥ d w + 1 1 + Δ + 1 1 . Combining the upper and lower bounds on ρ \rho ρ gives
1 d w + 1 < 2 Δ − 1 Δ + 1 = Δ + 2 Δ ( Δ + 1 ) , \frac{1}{d_w+1}<\frac{2}{\Delta}-\frac{1}{\Delta+1}=\frac{\Delta+2}{\Delta(\Delta+1)}, d w + 1 1 < Δ 2 − Δ + 1 1 = Δ ( Δ + 1 ) Δ + 2 ,
so
d w + 1 > Δ ( Δ + 1 ) Δ + 2 = Δ − 1 + 2 Δ + 2 . d_w+1>\frac{\Delta(\Delta+1)}{\Delta+2}=\Delta-1+\frac{2}{\Delta+2}. d w + 1 > Δ + 2 Δ ( Δ + 1 ) = Δ − 1 + Δ + 2 2 .
Since d w d_w d w is an integer, d w ≥ Δ − 1 d_w\ge\Delta-1 d w ≥ Δ − 1 , proving that Δ − δ ≤ 1 \Delta-\delta\le1 Δ − δ ≤ 1 .
Suppose now that G G G is not regular, with degrees k k k and k + 1 k+1 k + 1 ; by Proposition 2.5 , k ≥ 2 k\ge2 k ≥ 2 . Let w w w be a vertex of degree k k k and let u ≠ w u\ne w u = w achieve r w u = ρ r_{wu}=\rho r w u = ρ . By Lemma 7.3, u u u is adjacent to w w w , and since d u ∈ { k , k + 1 } d_u\in\{k,k+1\} d u ∈ { k , k + 1 } , the adjacent bound of Lemma 2.7 gives
ρ ≥ min { 2 k − 2 k 2 − 1 , 2 k − 1 k 2 + k − 1 } = 2 k − 1 k 2 + k − 1 . \rho\ge\min\left\{\frac{2k-2}{k^2-1},\frac{2k-1}{k^2+k-1}\right\}=\frac{2k-1}{k^2+k-1}. ρ ≥ min { k 2 − 1 2 k − 2 , k 2 + k − 1 2 k − 1 } = k 2 + k − 1 2 k − 1 .
Comparing this with the upper bound ρ ≤ ( 2 − 2 / n ) / ( k + 1 ) \rho\le(2-2/n)/(k+1) ρ ≤ ( 2 − 2/ n ) / ( k + 1 ) obtained at a vertex of degree Δ = k + 1 \Delta=k+1 Δ = k + 1 gives ( 2 k − 1 ) ( k + 1 ) ≤ ( 2 − 2 / n ) ( k 2 + k − 1 ) (2k-1)(k+1)\le(2-2/n)(k^2+k-1) ( 2 k − 1 ) ( k + 1 ) ≤ ( 2 − 2/ n ) ( k 2 + k − 1 ) , which rearranges to
n ≥ 2 ( k 2 + k − 1 ) k − 1 = 2 k + 4 + 2 k − 1 . n\ge\frac{2(k^2+k-1)}{k-1}=2k+4+\frac{2}{k-1}. n ≥ k − 1 2 ( k 2 + k − 1 ) = 2 k + 4 + k − 1 2 .
Since n n n is an integer, this yields n ≥ 2 k + 5 n\ge2k+5 n ≥ 2 k + 5 for k ≥ 3 k\ge3 k ≥ 3 and n ≥ 10 n\ge10 n ≥ 10 for k = 2 k=2 k = 2 . □
Proposition 7.4 should be compared with Theorem C. When only the row sums of R R R are required to coincide, the degrees can differ by ( 4 n + 1 − 5 ) / 4 (\sqrt{4n+1}-5)/4 ( 4 n + 1 − 5 ) /4 and there can be three or four distinct degrees; when the full rows are required to coincide as multisets, the degrees differ by at most one.
To rule out the remaining two-degree case { k , k + 1 } \{k,k+1\} { k , k + 1 } of Conjecture 7.2 when m ≥ 4 m\ge4 m ≥ 4 , spectral moments alone do not suffice because the constancy of L v v † L^\dagger_{vv} L v v † and ( L † ) v v 2 (L^\dagger)^2_{vv} ( L † ) v v 2 only constrains the moments of orders 0 , − 1 , − 2 0,-1,-2 0 , − 1 , − 2 of the local spectral measure. Any full proof must therefore use the 0 / − 1 0/-1 0/ − 1 off-diagonal structure of the Laplacian; Example 7.8 below shows that a related statement fails as soon as the edges carry weights. One local identity that brings the neighbourhood N ( v ) N(v) N ( v ) directly into play expresses the sum of the effective resistances between the neighbours of v v v as a linear function of d v d_v d v .
Lemma 7.5 (resistances among the neighbours of a vertex). For every vertex v v v of a connected graph G G G , with σ v = ∑ u ∼ v r u v \sigma_v = \sum_{u\sim v} r_{uv} σ v = ∑ u ∼ v r uv ,
∑ u ∈ N ( v ) ∑ w ∈ N ( v ) r u w = 2 d v ( σ v − 1 ) . \sum_{u\in N(v)}\sum_{w\in N(v)} r_{uw} = 2d_v(\sigma_v-1). u ∈ N ( v ) ∑ w ∈ N ( v ) ∑ r u w = 2 d v ( σ v − 1 ) . In particular, in a resistance-regular graph on n n n vertices, the resistances between the neighbours of v v v sum to 2 d v ( 1 − 2 / n ) 2d_v(1-2/n) 2 d v ( 1 − 2/ n ) .
Proof. Write a u = L u u † a_u=L^\dagger_{uu} a u = L uu † . The ( v , w ) (v,w) ( v , w ) entry of L L † = I − J / n LL^\dagger=I-J/n L L † = I − J / n reads d v L v w † − ∑ u ∼ v L u w † = δ v w − 1 / n d_vL^\dagger_{vw}-\sum_{u\sim v}L^\dagger_{uw}=\delta_{vw}-1/n d v L v w † − ∑ u ∼ v L u w † = δ v w − 1/ n ; taking w = v w=v w = v gives ∑ u ∼ v L u v † = d v a v − 1 + 1 / n \sum_{u\sim v}L^\dagger_{uv}=d_va_v-1+1/n ∑ u ∼ v L uv † = d v a v − 1 + 1/ n , and summing the general case over w ∼ v w\sim v w ∼ v gives ∑ u , w ∈ N ( v ) L u w † = d v ∑ w ∼ v L v w † + d v / n = d v ( d v a v − 1 + 1 / n ) + d v / n \sum_{u,w\in N(v)}L^\dagger_{uw}=d_v\sum_{w\sim v}L^\dagger_{vw}+d_v/n=d_v(d_va_v-1+1/n)+d_v/n ∑ u , w ∈ N ( v ) L u w † = d v ∑ w ∼ v L v w † + d v / n = d v ( d v a v − 1 + 1/ n ) + d v / n . By (1) , ∑ u , w ∈ N ( v ) r u w = 2 d v ∑ u ∼ v a u − 2 ∑ u , w ∈ N ( v ) L u w † = 2 d v ( ∑ u ∼ v a u − d v a v + 1 − 2 / n ) \sum_{u,w\in N(v)}r_{uw}=2d_v\sum_{u\sim v}a_u-2\sum_{u,w\in N(v)}L^\dagger_{uw}=2d_v(\sum_{u\sim v}a_u-d_va_v+1-2/n) ∑ u , w ∈ N ( v ) r u w = 2 d v ∑ u ∼ v a u − 2 ∑ u , w ∈ N ( v ) L u w † = 2 d v ( ∑ u ∼ v a u − d v a v + 1 − 2/ n ) , while σ v = ∑ u ∼ v ( a u + a v − 2 L u v † ) = ∑ u ∼ v a u − d v a v + 2 − 2 / n \sigma_v=\sum_{u\sim v}(a_u+a_v-2L^\dagger_{uv})=\sum_{u\sim v}a_u-d_va_v+2-2/n σ v = ∑ u ∼ v ( a u + a v − 2 L uv † ) = ∑ u ∼ v a u − d v a v + 2 − 2/ n . Comparing the two expressions gives the identity, and the last statement follows from Theorem 2.4 (iii).
Computationally, Conjecture 7.2 holds for all connected graphs on at most 10 vertices: for all 11 989 762 of them, the stable resistance-based colouring coincides with the partition into automorphism orbits (an exact statement, since the resistances were computed exactly, the orbits refine the stable colouring and hash collisions can only merge colour classes), so a graph with a single colour class is vertex-transitive. It also holds for all 3.6 × 10 11 3.6 \times10^{11} 3.6 × 1 0 11 bi-Cayley graphs of § 4.1 . The hypothesis of the conjecture differs from walk-regularity even for regular graphs: the non-vertex-transitive walk-regular graphs on 12 vertices, the Folkman graph and the Gray graph have distinct row multisets, and among about 33 000 small regular graphs (all cubic graphs on at most 16 vertices, the 4-regular graphs on at most 13, the 5-regular graphs on 10 and 12, and the 6-regular graphs on 11 and 12 vertices) every graph whose resistance rows coincide as multisets is vertex-transitive.
The second resistance moment
The proof of Proposition 7.4 uses only the smallest entry of each row of R R R . The examples suggest that a single further statistic of a row, its second moment, already determines the degree in every resistance-regular graph. For a vertex v v v write S 2 ( v ) = ∑ u ∈ V r v u 2 S_2(v)=\sum_{u\in V}r_{vu}^{2} S 2 ( v ) = ∑ u ∈ V r v u 2 . By (18) , in a resistance-regular graph S 2 ( v ) S_2(v) S 2 ( v ) differs from 4 ( L † 2 ) v v 4(L^\dagger{}^2)_{vv} 4 ( L † 2 ) v v by a quantity that does not depend on v v v .
Conjecture 7.6. Let G G G be a connected resistance-regular graph and let u , v ∈ V u,v\in V u , v ∈ V . If d u < d v d_u<d_v d u < d v , then S 2 ( u ) < S 2 ( v ) S_2(u)<S_2(v) S 2 ( u ) < S 2 ( v ) ; equivalently, ( L † 2 ) u u < ( L † 2 ) v v (L^\dagger{}^2)_{uu}<(L^\dagger{}^2)_{vv} ( L † 2 ) uu < ( L † 2 ) v v .
If all rows of R R R are permutations of one another, then G G G is resistance-regular and S 2 S_2 S 2 is constant, so Conjecture 7.6 implies Conjecture 7.2. Similarly, if both L † L^\dagger L † and ( L † ) 2 (L^\dagger)^2 ( L † ) 2 have constant diagonal, then G G G is resistance-regular and, by (18) , S 2 S_2 S 2 is constant. Hence Conjecture 7.6 implies that a connected graph in which L † L^\dagger L † and ( L † ) 2 (L^\dagger)^2 ( L † ) 2 both have constant diagonal is regular; in other words, the first two of the conditions in Theorem A(i) would force regularity, whatever the value of m m m . For m ≤ 2 m\leq2 m ≤ 2 the first condition suffices (Theorem A(ii)), and for m = 3 m=3 m = 3 the two conditions are all of Theorem A(i). Since S 2 ( v ) S_2(v) S 2 ( v ) is determined by the multiset { { r v u : u ∈ V } } \{\{r_{vu}:u\in V\}\} {{ r v u : u ∈ V }} , Conjecture 7.6 would also imply that in a resistance-regular graph the first round of the resistance-based Weisfeiler–Leman test already separates vertices of different degrees.
The conjecture holds in every example known to us. We verified it in exact rational arithmetic for all graphs of Table 2 and Table 3 , for all 138 graphs of the ancillary catalogue (for the graphs with three and four degrees, the inequality holds between every pair of degree classes), and for the 3654 members of the four-parameter family of Appendix § 9 that our searches produced and that are listed in the ancillary files. It can also be proved in several cases.
Proposition 7.7. Conjecture 7.6 holds in each of the following cases:
L L L has exactly three distinct nonzero eigenvalues;
L L L has exactly four distinct nonzero eigenvalues, with sum σ 1 \sigma_1 σ 1 , and d u + d v + 1 < σ 1 d_u+d_v+1<\sigma_1 d u + d v + 1 < σ 1 whenever d u < d v d_u<d_v d u < d v ;
G = F ( p ) G=\mathcal{F}(p) G = F ( p ) for an even p ≥ 4 p\ge4 p ≥ 4 ;
G = C 6 ( t , t 2 ) G=C_6(t,t^2) G = C 6 ( t , t 2 ) for an integer t ≥ 2 t\ge2 t ≥ 2 ;
G G G is obtained by the construction of Proposition 5.5 from a graph H H H that satisfies Conjecture 7.6 .
Proof. Case (a) is Corollary 3.3 . For (b), let σ 1 , … , σ 4 \sigma_1,\ldots,\sigma_4 σ 1 , … , σ 4 be the elementary symmetric functions of the four distinct nonzero eigenvalues. By Lemma 3.1 with m = 4 m=4 m = 4 and j = 2 j=2 j = 2 , L 2 − σ 1 L + σ 2 P − σ 3 L † + σ 4 ( L † ) 2 = 0 L^2-\sigma_1L+\sigma_2P-\sigma_3L^\dagger+\sigma_4(L^\dagger)^2=0 L 2 − σ 1 L + σ 2 P − σ 3 L † + σ 4 ( L † ) 2 = 0 , where P = I − J / n P=I-J/n P = I − J / n . On the diagonal, with L v v † L^\dagger_{vv} L v v † constant, this yields
σ 4 ( ( ( L † ) 2 ) v v − ( ( L † ) 2 ) u u ) = ( d v − d u ) ( σ 1 − 1 − d u − d v ) . \sigma_4\left(((L^\dagger)^2)_{vv}-((L^\dagger)^2)_{uu}\right)=(d_v-d_u)(\sigma_1-1-d_u-d_v). σ 4 ( (( L † ) 2 ) v v − (( L † ) 2 ) uu ) = ( d v − d u ) ( σ 1 − 1 − d u − d v ) .
which has the sign of d v − d u d_v-d_u d v − d u under the stated condition. For (c), the diagonal of ( L † ) 2 (L^\dagger)^2 ( L † ) 2 at ( h , i ) (h,i) ( h , i ) is the average of the ( i , i ) (i,i) ( i , i ) entries of ( L ^ χ † ) 2 (\widehat{L}_{\chi}^{\dagger})^2 ( L χ † ) 2 over all characters χ \chi χ , as in the proof of Lemma 4.2 . Evaluating these averages with the table of Lemma 4.4 shows that between a vertex v ∈ Q b v\in Q_b v ∈ Q b (degree 2 p − 1 2p-1 2 p − 1 ) and a vertex w ∈ X b w\in X_b w ∈ X b (degree 2 p − 2 2p-2 2 p − 2 ),
( ( L † ) 2 ) v v − ( ( L † ) 2 ) w w = 7 p − 6 8 p 2 ( p − 1 ) ( p − 2 ) > 0. ((L^\dagger)^2)_{vv}-((L^\dagger)^2)_{ww}=\frac{7p-6}{8p^2(p-1)(p-2)}>0. (( L † ) 2 ) v v − (( L † ) 2 ) w w = 8 p 2 ( p − 1 ) ( p − 2 ) 7 p − 6 > 0.
for F ( 4 ) \mathcal{F}(4) F ( 4 ) , this gives S 2 ( v ) = 371 / 128 S_2(v)=371/128 S 2 ( v ) = 371/128 at vertices of degree 7 and 1069 / 384 1069/384 1069/384 at vertices of degree 6. For (d), Proposition 5.3 together with the values y ( 0 ) y^{(0)} y ( 0 ) and y ( 1 ) y^{(1)} y ( 1 ) in the proof of Lemma 6.1 gives, for w w w in a clique module and v v v in an independent module of C 6 ( t , t 2 ) C_6(t,t^2) C 6 ( t , t 2 ) ,
( ( L † ) 2 ) w w − ( ( L † ) 2 ) v v = ( t − 1 ) ( 4 t 2 + 2 t + 1 ) 8 t 6 ( 2 t + 1 ) > 0. ((L^\dagger)^2)_{ww}-((L^\dagger)^2)_{vv}=\frac{(t-1)(4t^2+2t+1)}{8t^6(2t+1)}>0. (( L † ) 2 ) w w − (( L † ) 2 ) v v = 8 t 6 ( 2 t + 1 ) ( t − 1 ) ( 4 t 2 + 2 t + 1 ) > 0.
Case (e) follows from the second formula of Proposition 5.5, since the substitution preserves the order of the degrees.
For graphs 14 and 15 of Table 2 , which have m = 4 m=4 m = 4 , the nonzero eigenvalues 12, 16 and 12 ± 4 5 12\pm4\sqrt{5} 12 ± 4 5 have sum 52 > 14 + 15 + 1 >14+15+1 > 14 + 15 + 1 , in accordance with (b).
The conjecture depends on the edges having equal weights. For a graph with positive edge weights, the weighted Laplacian, its pseudoinverse, the effective resistances and the weighted degrees are defined in the usual way, and Theorem 2.4 (ii) and (18) remain valid.
Example 7.8. Let H H H be the house graph on the vertices 0 , … , 4 0,\ldots,4 0 , … , 4 , consisting of the 4-cycle 0 , 3 , 1 , 4 0,3,1,4 0 , 3 , 1 , 4 and the roof vertex 2 adjacent to 0 and 4, with edge weights w 02 = w 24 = 360 w_{02}=w_{24}=360 w 02 = w 24 = 360 , w 03 = w 14 = 273 w_{03}=w_{14}=273 w 03 = w 14 = 273 , w 04 = 15 w_{04}=15 w 04 = 15 and w 13 = 455 w_{13}=455 w 13 = 455 . The weighted degrees of the vertices 0, 1, 2, 3, 4 are 648, 728, 720, 728 and 648, and every diagonal entry of the pseudoinverse of the weighted Laplacian equals 121 / 102375 121/102375 121/102375 , so H H H is resistance-regular in the weighted sense. Nevertheless S 2 ( 2 ) − S 2 ( 1 ) = 79 / 1117935000 > 0 S_2(2)-S_2(1)=79/1117935000>0 S 2 ( 2 ) − S 2 ( 1 ) = 79/1117935000 > 0 , although vertex 2 has smaller weighted degree than vertex 1.
Thus no argument that applies verbatim to weighted graphs can prove Conjecture 7.6 . The conjecture also has a probabilistic reading. Let η v \eta_v η v be the hitting time of v v v for the continuous-time random walk on G G G that crosses each edge at rate 1, started from a uniformly random vertex. The expected hitting time from u u u , ψ ( u ) = n ( L v w † − L u w † ) \psi(u)=n(L^\dagger_{vw}-L^\dagger_{uw}) ψ ( u ) = n ( L v w † − L u w † ) , satisfies ( L ψ ) ( u ) = 1 (L\psi)(u)=1 ( L ψ ) ( u ) = 1 for u ≠ v u\ne v u = v and ψ ( v ) = 0 \psi(v)=0 ψ ( v ) = 0 , and a similar computation for the second moment gives
E η v = n L v v † , Var η v = 2 n ( ( L † ) 2 ) v v + n 2 ( L v v † ) 2 . \mathbb{E}\,\eta_v=nL^\dagger_{vv},\qquad\operatorname{Var}\eta_v=2n((L^\dagger)^2)_{vv}+n^2(L^\dagger_{vv})^2. E η v = n L v v † , Var η v = 2 n (( L † ) 2 ) v v + n 2 ( L v v † ) 2 .
In a resistance-regular graph all vertices are thus equally hard to hit on average, and Conjecture 7.6 states that the hitting time of a vertex of larger degree has the larger variance. We intend to study Conjecture 7.6 further in a separate paper.
Consequences and open problems
Resistance-regularity appears under several names in combinatorics, network analysis and machine learning, and our results have the following consequences.
Resistance curvature. The vertex curvature p v = 1 − 1 2 ∑ u ∼ v r u v p_v = 1 - \frac{1}{2}\sum_{u\sim v} r_{uv} p v = 1 − 2 1 ∑ u ∼ v r uv of Devriendt and Lambiotte [20 ] is constant if and only if G G G is resistance-regular. Theorem B therefore gives the first infinite family of non-regular graphs with constant resistance curvature, answering the question raised in [21 ] , where all known examples were vertex-transitive [21 , 23 ] . By Theorem C, the degrees of such a graph can differ by about n / 2 \sqrt{n}/2 n /2 , and there can be three or four of them.
Current-flow closeness centrality. The current-flow closeness of Brandes and Fleischer [9 ] , equivalent up to scaling to the information centrality of Stephenson and Zelen [8 ] , is ( n − 1 ) / R v (n-1)/R_v ( n − 1 ) / R v . In a resistance-regular graph all vertices have the same current-flow closeness, even when their degrees differ, by t − 1 t-1 t − 1 in C 6 ( t , t 2 ) C_6(t,t^2) C 6 ( t , t 2 ) ; by Proposition 6.3, a large difference of degrees then forces a small algebraic connectivity.
Uniform spanning trees. By (3) and Theorem 2.4(iii), in a uniformly random spanning tree of a resistance-regular graph the degree of every vertex has expectation 2 ( n − 1 ) / n 2(n-1)/n 2 ( n − 1 ) / n . Higher moments still distinguish the degree classes: in F ( 4 ) \mathcal{F}(4) F ( 4 ) , the variance of the tree degree is about 0.682 at a vertex of degree 6 and 0.742 at a vertex of degree 7.
Distance-based Weisfeiler–Leman tests. Zhang et al. [10 ] studied the generalised distance Weisfeiler–Leman test, which refines the colour of v v v by the multiset { ( d ( v , u ) , colour ( u ) ) : u ∈ V } \{(d(v,u),\operatorname{colour}(u)): u\in V\} {( d ( v , u ) , colour ( u )) : u ∈ V } for a graph metric d d d . For shortest-path distance the first round refines the degree partition; for effective resistance it is open whether even the stable colouring does. Flora et al. [36 ] conjecture that the stable resistance-based colouring can fail to distinguish graphs that the classical test distinguishes; since the classical test refines the degree partition, a negative answer to our question would point towards their conjecture. For resistance-regular graphs, Conjecture 7.6 would imply that already the first round separates vertices of different degrees.
Open questions. We close by recording the main questions left open by our results:
Minimum order. What is the smallest number of vertices of a non-regular resistance-regular graph? By Proposition 3.4 and Theorem B, it lies between 13 and 16.
Three nonzero Laplacian eigenvalues. Theorem A(ii) rules out m ≤ 2 m\le2 m ≤ 2 , and Proposition 4.8 provides examples with m = 4 m=4 m = 4 . Does there exist a connected non-regular resistance-regular graph with m = 3 m=3 m = 3 ? By Theorem A(ii), it would have exactly two degrees, adding up to one less than the sum of the three eigenvalues.
Difference of degrees. What is the order of growth of the largest difference g ( n ) g(n) g ( n ) between the maximum and the minimum degree of a resistance-regular graph on n n n vertices? We know that g ( n ) ≥ ( 4 n + 1 − 5 ) / 4 g(n)\ge(\sqrt{4n+1}-5)/4 g ( n ) ≥ ( 4 n + 1 − 5 ) /4 for n = 4 t 2 + 2 t n=4t^2+2t n = 4 t 2 + 2 t and that g ( n ) < n / 2 g(n)<n/2 g ( n ) < n /2 , and ( 2 − 3 ) n (2-\sqrt{3})n ( 2 − 3 ) n is an upper bound when there are only two distinct degrees.
Number of degrees and symmetry. Is the number of distinct degrees of a resistance-regular graph bounded? Is there a non-regular resistance-regular graph with a trivial automorphism
group? All examples known to us are built from modules or have a large automorphism group.
Rows of the resistance matrix and diagonal powers. Do Conjectures 7.2 and 7.6 hold? In particular, is every connected graph in which both L † L^\dagger L † and ( L † ) 2 (L^\dagger)^2 ( L † ) 2 have constant diagonal regular? More generally, which combinations of resistance-based vertex invariants suffice to determine the degree of a vertex?
Declaration of generative AI and AI-assisted technologies. During the preparation of this work, the authors used Claude Fable 5.1 to assist with writing the computational search scripts and brainstorming initial lines of inquiry, and Gemini Argon to assist with structuring, drafting and editing the manuscript text. After using these tools, the authors independently verified all mathematical proofs and exact computations, reviewed and edited the text as needed, and take full responsibility for the content of the publication.
The four-parameter family
Let s , a , k ≥ 1 s,a,k \ge1 s , a , k ≥ 1 and h ≥ 2 h \ge2 h ≥ 2 be integers. The graph G ( s , a , k , h ) \mathcal{G}(s,a,k,h) G ( s , a , k , h ) has vertex set ⋃ b < s ( Q b ∪ X b ) \bigcup_{b<s}(Q_b \cup X_b) ⋃ b < s ( Q b ∪ X b ) , where the Q b Q_b Q b are disjoint sets of size a a a and X b = { x b , c , t : c < k , t < h } X_b = \{x_{b,c,t}: c<k,\ t<h\} X b = { x b , c , t : c < k , t < h } . Every Q b Q_b Q b is a clique, every vertex of Q b Q_b Q b is adjacent to every vertex of X b X_b X b , and x b , c , t ∼ x b ′ , c ′ , t ′ x_{b,c,t} \sim x_{b',c',t'} x b , c , t ∼ x b ′ , c ′ , t ′ if and only if c = c ′ c=c' c = c ′ and t ≠ t ′ t\ne t' t = t ′ . Thus, for each c < k c<k c < k , the s h sh s h vertices x b , c , t x_{b,c,t} x b , c , t induce the complete multipartite graph whose h h h parts { x b , c , t : b < s } \{x_{b,c,t}: b<s\} { x b , c , t : b < s } have size s s s . The graph is connected and has n = s ( a + k h ) n=s(a+kh) n = s ( a + k h ) vertices; a vertex of Q b Q_b Q b has degree a − 1 + k h a-1+kh a − 1 + k h and a vertex of X b X_b X b has degree a + s ( h − 1 ) a+s(h-1) a + s ( h − 1 ) , so the two degrees differ by k h − 1 − s ( h − 1 ) kh-1-s(h-1) k h − 1 − s ( h − 1 ) . Comparing with Definition 4.3 shows that G ( 2 , p , 2 , p / 2 ) = F ( p ) \mathcal{G}(2,p,2,p/2)=\mathcal{F}(p) G ( 2 , p , 2 , p /2 ) = F ( p ) . In this appendix only, we write
E = a + k h , F = a + s ( h − 1 ) , H = a + s h , D = k h s ( h − 1 ) . E=a+kh,\qquad F=a+s(h-1),\qquad H=a+sh,\qquad D=khs(h-1). E = a + k h , F = a + s ( h − 1 ) , H = a + s h , D = k h s ( h − 1 ) .
Proposition A.1. The Laplacian eigenvalues of G ( s , a , k , h ) \mathcal{G}(s,a,k,h) G ( s , a , k , h ) are 0 0 0 ; E E E with multiplicity s ( a − 1 ) + 1 s(a-1)+1 s ( a − 1 ) + 1 ; a a a with multiplicity k − 1 k-1 k − 1 ; H H H with multiplicity k ( h − 1 ) k(h-1) k ( h − 1 ) ; F F F with multiplicity ( s − 1 ) ( k h − 1 ) (s-1)(kh-1) ( s − 1 ) ( k h − 1 ) ; and the two roots μ ± \mu_\pm μ ± of μ 2 − ( k h + F ) μ + D \mu^2-(kh+F)\mu+D μ 2 − ( k h + F ) μ + D , each with multiplicity s − 1 s-1 s − 1 .
Proof. We decompose R V \mathbb{R}^{V} R V into mutually orthogonal subspaces invariant under L L L :
vectors supported on a single Q b Q_b Q b whose entries sum to zero (dimension s ( a − 1 ) s(a-1) s ( a − 1 ) );
vectors supported on ⋃ b X b \bigcup_b X_b ⋃ b X b whose value at x b , c , t x_{b,c,t} x b , c , t depends only on c c c and sums to zero over c c c (dimension k − 1 k-1 k − 1 );
vectors supported on ⋃ b X b \bigcup_b X_b ⋃ b X b whose value at x b , c , t x_{b,c,t} x b , c , t depends only on ( c , t ) (c,t) ( c , t ) and sums to zero over t t t for every c c c (dimension k ( h − 1 ) k(h-1) k ( h − 1 ) );
vectors supported on ⋃ b X b \bigcup_b X_b ⋃ b X b whose values sum to zero over b b b for every ( c , t ) (c,t) ( c , t ) and over ( c , t ) (c,t) ( c , t ) for every b b b (dimension ( s − 1 ) ( k h − 1 ) (s-1)(kh-1) ( s − 1 ) ( k h − 1 ) );
vectors that are constant on every Q b Q_b Q b and on every X b X_b X b (dimension 2 s 2s 2 s ).
On (1), L L L acts as E E E by Lemma 5.2 , since Q b Q_b Q b is a clique module with k h kh k h outside neighbours. At a vertex q ∈ Q b q\in Q_b q ∈ Q b , a vector f f f in (2), (3) or (4) gives ( L f ) ( q ) = − ∑ x ∈ X b f ( x ) = 0 (Lf)(q)=-\sum_{x\in X_b}f(x)=0 ( L f ) ( q ) = − ∑ x ∈ X b f ( x ) = 0 , by the zero-sum conditions. At a vertex x = x b , c , t x=x_{b,c,t} x = x b , c , t , ( L f ) ( x ) = ( a + s ( h − 1 ) ) f ( x ) − ∑ f ( x b ′ , c , t ′ ) (Lf)(x)=(a+s(h-1))f(x)-\sum f(x_{b',c,t'}) ( L f ) ( x ) = ( a + s ( h − 1 )) f ( x ) − ∑ f ( x b ′ , c , t ′ ) , the sum running over b ′ < s b'<s b ′ < s and t ′ ≠ t t'\ne t t ′ = t ; this sum equals s ( h − 1 ) f ( x ) s(h-1)f(x) s ( h − 1 ) f ( x ) in (2), − s f ( x ) -sf(x) − s f ( x ) in (3) and 0 0 0 in (4), so L L L acts as a a a , H H H and F F F respectively. Finally, if f ∈ ( 5 ) f\in(5) f ∈ ( 5 ) takes the value α b \alpha_b α b on Q b Q_b Q b and β b \beta_b β b on X b X_b X b , then L f Lf L f takes the values k h ( α b − β b ) kh(\alpha_b-\beta_b) k h ( α b − β b ) on Q b Q_b Q b and a ( β b − α b ) + s ( h − 1 ) β b − ( h − 1 ) ∑ b ′ β b ′ a(\beta_b-\alpha_b)+s(h-1)\beta_b-(h-1)\sum_{b'}\beta_{b'} a ( β b − α b ) + s ( h − 1 ) β b − ( h − 1 ) ∑ b ′ β b ′ on X b X_b X b . On the vectors with α b , β b \alpha_b,\beta_b α b , β b independent of b b b this is the matrix ( k h − k h − a a ) \left(\begin{smallmatrix}kh&-kh\\-a&a\end{smallmatrix}\right) ( k h − a − k h a ) , with eigenvalues 0 0 0 and E E E , and on the vectors with ∑ b α b = ∑ b β b = 0 \sum_b\alpha_b=\sum_b\beta_b=0 ∑ b α b = ∑ b β b = 0 it acts on every pair ( α b , β b ) (\alpha_b,\beta_b) ( α b , β b ) by the matrix
M = ( k h − k h − a F ) , det M = k h ( F − a ) = D , M=\begin{pmatrix}kh&-kh\\-a&F\end{pmatrix},\qquad\det M=kh(F-a)=D, M = ( k h − a − k h F ) , det M = k h ( F − a ) = D ,
whose eigenvalues are μ ± \mu_{\pm} μ ± , each with multiplicity s − 1 s-1 s − 1 . The dimensions add up to s ( a − 1 ) + ( k − 1 ) + k ( h − 1 ) + ( s − 1 ) ( k h − 1 ) + 2 s = n s(a-1)+(k-1)+k(h-1)+(s-1)(kh-1)+2s=n s ( a − 1 ) + ( k − 1 ) + k ( h − 1 ) + ( s − 1 ) ( k h − 1 ) + 2 s = n .
Proposition A.2. For q ∈ Q b q\in Q_b q ∈ Q b and x ∈ X b x\in X_b x ∈ X b ,
L q q † = 1 s a ( s ( a − 1 ) E + k h E 2 + ( s − 1 ) F D ) , L^\dagger_{qq}=\frac{1}{sa}\left(\frac{s(a-1)}{E}+\frac{kh}{E^2}+\frac{(s-1)F}{D}\right), L q q † = s a 1 ( E s ( a − 1 ) + E 2 k h + D ( s − 1 ) F ) , L x x † = 1 s k h ( k − 1 a + k ( h − 1 ) H + ( s − 1 ) ( k h − 1 ) F + a E 2 + s − 1 s ( h − 1 ) ) , L^\dagger_{xx}=\frac{1}{skh}\left(\frac{k-1}{a}+\frac{k(h-1)}{H}+\frac{(s-1)(kh-1)}{F}+\frac{a}{E^2}+\frac{s-1}{s(h-1)}\right), L xx † = s k h 1 ( a k − 1 + H k ( h − 1 ) + F ( s − 1 ) ( k h − 1 ) + E 2 a + s ( h − 1 ) s − 1 ) , and
L q q † − L x x † = N ( s , a , k , h ) a h k s ( a + h k ) ( a + h s ) ( a + h s − s ) , L^\dagger_{qq}-L^\dagger_{xx}=\frac{N(s,a,k,h)}{ahks(a+hk)(a+hs)(a+hs-s)}, L q q † − L xx † = ahk s ( a + hk ) ( a + h s ) ( a + h s − s ) N ( s , a , k , h ) , where
N ( s , a , k , h ) = 2 ( s − 1 ) a 3 + s ( h 2 k s − h 2 k 2 − h k s + h k + 3 h s − 3 h − s + 1 ) a 2 + h s ( h 2 k s 2 − h 2 k 2 s − h k s 2 + h k + h s 2 − h s + k s − k − s 2 + s ) a − h 2 k s 2 ( h − 1 ) ( k − 1 ) . \begin{aligned}
N(s,a,k,h)={}&2(s-1)a^3+s(h^2ks-h^2k^2-hks+hk+3hs-3h-s+1)a^2\\
&+hs(h^2ks^2-h^2k^2s-hks^2+hk+hs^2-hs+ks-k-s^2+s)a\\
&-h^2ks^2(h-1)(k-1).
\end{aligned} N ( s , a , k , h ) = 2 ( s − 1 ) a 3 + s ( h 2 k s − h 2 k 2 − hk s + hk + 3 h s − 3 h − s + 1 ) a 2 + h s ( h 2 k s 2 − h 2 k 2 s − hk s 2 + hk + h s 2 − h s + k s − k − s 2 + s ) a − h 2 k s 2 ( h − 1 ) ( k − 1 ) . Consequently, G ( s , a , k , h ) G(s,a,k,h) G ( s , a , k , h ) is resistance-regular if and only if N ( s , a , k , h ) = 0 N(s,a,k,h)=0 N ( s , a , k , h ) = 0 .
Proof. Since the subspaces in the proof of Proposition A.1 are orthogonal and invariant, L v v † L^\dagger_{vv} L v v † is the sum over them of e v T L † z v e_v^{\mathsf T}L^\dagger z_v e v T L † z v , where z v z_v z v is the orthogonal projection of e v e_v e v onto the subspace; on a subspace on which L L L acts as a scalar μ \mu μ , this is ∥ z v ∥ 2 / μ \lVert z_v\rVert^2/\mu ∥ z v ∥ 2 / μ . For q q q , the squared norms of the projections onto (1)–(4) are 1 − 1 / a 1-1/a 1 − 1/ a , 0 0 0 , 0 0 0 , 0 0 0 . For x x x they are 0 0 0 , ( k − 1 ) / ( s k h ) (k-1)/(skh) ( k − 1 ) / ( s k h ) , ( h − 1 ) / ( s h ) = k ( h − 1 ) / ( s k h ) (h-1)/(sh)=k(h-1)/(skh) ( h − 1 ) / ( s h ) = k ( h − 1 ) / ( s k h ) and ( s − 1 ) ( k h − 1 ) / ( s k h ) (s-1)(kh-1)/(skh) ( s − 1 ) ( k h − 1 ) / ( s k h ) , the last because the vectors in (4) are those that sum to zero over b b b , minus those that are constant on every X b X_b X b . In (5), the eigenvector for E E E orthogonal to 1 \mathbf{1} 1 is the vector u u u with value k h kh k h on every Q b Q_b Q b and − a -a − a on every X b X_b X b ; since ∥ u ∥ 2 = s a k h E \lVert u\rVert^2=sakhE ∥ u ∥ 2 = s ak h E , it contributes k h / ( s a E 2 ) kh/(saE^2) k h / ( s a E 2 ) at q q q and a / ( s k h E 2 ) a/(skhE^2) a / ( s k h E 2 ) at x x x . The projection of e q e_q e q onto the remaining part of (5) has α b ′ = ( δ b b ′ − 1 / s ) / a \alpha_{b'}=(\delta_{bb'}-1/s)/a α b ′ = ( δ b b ′ − 1/ s ) / a and β = 0 \beta=0 β = 0 , and applying L † L^\dagger L † means applying
M − 1 = D − 1 ( F k h a k h ) M^{-1}=D^{-1}\begin{pmatrix}F&kh\\a&kh\end{pmatrix} M − 1 = D − 1 ( F a k h k h )
to every pair; the value at q q q is therefore ( 1 − 1 / s ) ( M − 1 ) 11 / a = ( s − 1 ) F / ( s a D ) (1-1/s)(M^{-1})_{11}/a=(s-1)F/(saD) ( 1 − 1/ s ) ( M − 1 ) 11 / a = ( s − 1 ) F / ( s a D ) . Similarly, the projection of e x e_x e x has α = 0 \alpha=0 α = 0 and β b ′ = ( δ b b ′ − 1 / s ) / ( k h ) \beta_{b'}=(\delta_{bb'}-1/s)/(kh) β b ′ = ( δ b b ′ − 1/ s ) / ( k h ) , and it contributes ( 1 − 1 / s ) ( M − 1 ) 22 / ( k h ) = ( s − 1 ) / ( s D ) (1-1/s)(M^{-1})_{22}/(kh)=(s-1)/(sD) ( 1 − 1/ s ) ( M − 1 ) 22 / ( k h ) = ( s − 1 ) / ( sD ) . Adding up gives the two formulas, and bringing their difference to a common denominator, a routine computation that the ancillary files carry out symbolically, gives the last one. The denominator is positive, so L † L^\dagger L † has constant diagonal if and only if N ( s , a , k , h ) = 0 N(s,a,k,h)=0 N ( s , a , k , h ) = 0 .
The same decomposition gives closed formulas for the diagonal of ( L † ) 2 (L^\dagger)^2 ( L † ) 2 ; they are checked in the ancillary scripts, and we used them to check Conjecture 7.6 for the members of the family listed below.
As a polynomial in k k k , N N N has negative leading coefficient − h 2 s ( a 2 + a h s + s ( h − 1 ) ) -h^2s(a^2+ahs+s(h-1)) − h 2 s ( a 2 + ah s + s ( h − 1 )) and positive constant term a ( s − 1 ) ( a + h s ) ( 2 a + h s − s ) a(s-1)(a+hs)(2a+hs-s) a ( s − 1 ) ( a + h s ) ( 2 a + h s − s ) , so for given s ≥ 2 s\geq2 s ≥ 2 , a a a and h h h there is exactly one positive real k k k with N = 0 N=0 N = 0 . Integer solutions are rarer, but they include a two-parameter family.
Corollary A.3. For integers h ≥ 2 h\geq2 h ≥ 2 and m ≥ 0 m\geq0 m ≥ 0 , put s = h m + 2 s=hm+2 s = hm + 2 , k = ( h + 1 ) m + 2 k=(h+1)m+2 k = ( h + 1 ) m + 2 and a = s h ( k − 1 ) a=sh(k-1) a = s h ( k − 1 ) . Then G ( s , a , k , h ) G(s,a,k,h) G ( s , a , k , h ) is a connected resistance-regular graph on n = h s ( h ( h + 1 ) m 2 + ( 4 h + 3 ) m + 4 ) n=hs(h(h+1)m^2+(4h+3)m+4) n = h s ( h ( h + 1 ) m 2 + ( 4 h + 3 ) m + 4 ) vertices whose two degrees differ by 2 h m + 1 = 2 s − 3 2hm+1=2s-3 2 hm + 1 = 2 s − 3 . For m = 0 m=0 m = 0 it is F ( 2 h ) \mathcal{F}(2h) F ( 2 h ) .
Proof. A direct expansion gives the polynomial identity N ( s , s h ( k − 1 ) , k , h ) = h 2 k s 3 ( k − 1 ) ( h k − 1 ) ( s ( h + 1 ) − h k − 2 ) N(s,sh(k-1),k,h)=h^{2}k s^{3}(k-1)(hk-1)(s(h+1)-hk-2) N ( s , s h ( k − 1 ) , k , h ) = h 2 k s 3 ( k − 1 ) ( hk − 1 ) ( s ( h + 1 ) − hk − 2 ) , and s ( h + 1 ) − h k − 2 = 0 s(h+1)-hk-2=0 s ( h + 1 ) − hk − 2 = 0 for the given s s s and k k k . The remaining statements follow from the formulas for n n n and for the degrees.
Since n n n is of order m 3 m^{3} m 3 for fixed h h h , the degrees in Corollary A.3 differ by an amount of order n 1 / 3 n^{1/3} n 1/3 , less than in Theorem C(i). Table 4 lists, for each difference of degrees, the smallest member of the family found in a computer search over all parameters with s ≤ 4000 s\le4000 s ≤ 4000 and difference at most 12 in absolute value; a negative difference means that the vertices of X b X_b X b have the larger degree. In this range, 2 is the only even difference that occurs. The family is infinite, since it contains all F ( p ) \mathcal{F}(p) F ( p ) and all graphs of Corollary A.3; our searches, which also covered other ranges of parameters, produced a list of 3654 members, given in the ancillary files, and each of them satisfies Conjecture 7.6 .
Table 4. The smallest members of G ( s , a , k , h ) \mathcal{G}(s,a,k,h) G ( s , a , k , h ) found for each difference of degrees k h − 1 − s ( h − 1 ) kh-1-s(h-1) k h − 1 − s ( h − 1 ) ; the member with difference 1 is F ( 4 ) \mathcal{F}(4) F ( 4 ) .
Connection sets and ancillary files
Each of the sixteen non-regular resistance-regular graphs in Table 2 is realised below as BiCay ( H ; S 11 , S 22 , S 12 ) \operatorname{BiCay}(H;S_{11},S_{22},S_{12}) BiCay ( H ; S 11 , S 22 , S 12 ) for a group H H H . Elements of Z a × Z b \mathbb{Z}_a\times\mathbb{Z}_b Z a × Z b are written as pairs, elements of Z 2 × Z 2 × Z 4 \mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_4 Z 2 × Z 2 × Z 4 as triples, elements of the dihedral group D k = ⟨ r , s ∣ r k = s 2 = 1 , s r s = r − 1 ⟩ D_k=\langle r,s\mid r^k=s^2=1,\ srs=r^{-1}\rangle D k = ⟨ r , s ∣ r k = s 2 = 1 , sr s = r − 1 ⟩ as r i r^i r i or r i s r^i s r i s , and elements of the dicyclic group Dic 3 = ⟨ a , x ∣ a 6 = 1 , x 2 = a 3 , x a x − 1 = a − 1 ⟩ \operatorname{Dic}_3=\langle a,x\mid a^6=1,\ x^2=a^3,\ xax^{-1}=a^{-1}\rangle Dic 3 = ⟨ a , x ∣ a 6 = 1 , x 2 = a 3 , x a x − 1 = a − 1 ⟩ as a i a^i a i or a i x a^i x a i x . For non-abelian H H H , edges are given by right multiplication: ( h , 1 ) ∼ ( h s , 1 ) (h,1)\sim(hs,1) ( h , 1 ) ∼ ( h s , 1 ) for s ∈ S 11 s\in S_{11} s ∈ S 11 , ( h , 2 ) ∼ ( h s , 2 ) (h,2)\sim(hs,2) ( h , 2 ) ∼ ( h s , 2 ) for s ∈ S 22 s\in S_{22} s ∈ S 22 , and ( h , 1 ) ∼ ( h s , 2 ) (h,1)\sim(hs,2) ( h , 1 ) ∼ ( h s , 2 ) for s ∈ S 12 s\in S_{12} s ∈ S 12 .
Z 2 × Z 4 \mathbb{Z}_2\times\mathbb{Z}_4 Z 2 × Z 4 : S 11 = { ( 0 , 2 ) , ( 1 , 0 ) } S_{11}=\{(0,2),(1,0)\} S 11 = {( 0 , 2 ) , ( 1 , 0 )} , S 22 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) } S_{22}=\{(0,1),(0,2),(0,3)\} S 22 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 )} , S 12 = { 0 } × Z 4 S_{12}=\{0\}\times\mathbb{Z}_4 S 12 = { 0 } × Z 4 .
Dic 3 \operatorname{Dic}_3 Dic 3 : S 11 = { x , a 3 x } S_{11}=\{x,a^3x\} S 11 = { x , a 3 x } , S 22 = { a 3 , a x , a 4 x } S_{22}=\{a^3,ax,a^4x\} S 22 = { a 3 , a x , a 4 x } , S 12 = { 1 , a 3 , a x , a 4 x } S_{12}=\{1,a^3,ax,a^4x\} S 12 = { 1 , a 3 , a x , a 4 x } .
Z 12 \mathbb{Z}_{12} Z 12 : S 11 = { ± 1 , ± 2 } S_{11}=\{\pm1,\pm2\} S 11 = { ± 1 , ± 2 } , S 22 = { 2 , 4 , 6 , 8 , 10 } S_{22}=\{2,4,6,8,10\} S 22 = { 2 , 4 , 6 , 8 , 10 } , S 12 = { 0 , 6 } S_{12}=\{0,6\} S 12 = { 0 , 6 } .
Z 2 × Z 6 \mathbb{Z}_2\times\mathbb{Z}_6 Z 2 × Z 6 : S 11 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 4 ) , ( 0 , 5 ) } S_{11}=\{(0,1),(0,2),(0,4),(0,5)\} S 11 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 4 ) , ( 0 , 5 )} , S 22 = { ( 0 , 2 ) , ( 0 , 4 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 1 , 4 ) } S_{22}=\{(0,2),(0,4),(1,0),(1,2),(1,4)\} S 22 = {( 0 , 2 ) , ( 0 , 4 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 1 , 4 )} , S 12 = { ( 0 , 0 ) , ( 0 , 2 ) , ( 0 , 4 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 1 , 4 ) } S_{12}=\{(0,0),(0,2),(0,4),(1,0),(1,2),(1,4)\} S 12 = {( 0 , 0 ) , ( 0 , 2 ) , ( 0 , 4 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 1 , 4 )} .
Z 2 × Z 8 \mathbb{Z}_2\times\mathbb{Z}_8 Z 2 × Z 8 : S 11 = { ( 0 , 1 ) , ( 0 , 4 ) , ( 0 , 7 ) , ( 1 , 1 ) , ( 1 , 7 ) } S_{11}=\{(0,1),(0,4),(0,7),(1,1),(1,7)\} S 11 = {( 0 , 1 ) , ( 0 , 4 ) , ( 0 , 7 ) , ( 1 , 1 ) , ( 1 , 7 )} , S 22 = { ( 0 , 2 ) , ( 0 , 6 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 1 , 4 ) , ( 1 , 6 ) } S_{22}=\{(0,2),(0,6),(1,0),(1,2),(1,4),(1,6)\} S 22 = {( 0 , 2 ) , ( 0 , 6 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 1 , 4 ) , ( 1 , 6 )} , S 12 = { ( 0 , 0 ) , ( 0 , 4 ) } S_{12}=\{(0,0),(0,4)\} S 12 = {( 0 , 0 ) , ( 0 , 4 )} .
Z 4 × Z 4 \mathbb{Z}_4\times\mathbb{Z}_4 Z 4 × Z 4 : S 11 = { ( 0 , 1 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 2 , 2 ) , ( 3 , 0 ) } S_{11}=\{(0,1),(0,3),(1,0),(2,2),(3,0)\} S 11 = {( 0 , 1 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 2 , 2 ) , ( 3 , 0 )} , S 22 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 2 , 0 ) , ( 2 , 1 ) , ( 2 , 3 ) } S_{22}=\{(0,1),(0,2),(0,3),(2,0),(2,1),(2,3)\} S 22 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 2 , 0 ) , ( 2 , 1 ) , ( 2 , 3 )} , S 12 = { ( 0 , 0 ) , ( 0 , 2 ) , ( 2 , 0 ) , ( 2 , 2 ) } S_{12}=\{(0,0),(0,2),(2,0),(2,2)\} S 12 = {( 0 , 0 ) , ( 0 , 2 ) , ( 2 , 0 ) , ( 2 , 2 )} .
Z 4 × Z 4 \mathbb{Z}_4\times\mathbb{Z}_4 Z 4 × Z 4 : S 11 = { ( 0 , 1 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 3 , 0 ) , ( 3 , 3 ) } S_{11}=\{(0,1),(0,3),(1,0),(1,1),(3,0),(3,3)\} S 11 = {( 0 , 1 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 3 , 0 ) , ( 3 , 3 )} , S 22 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 2 , 0 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 ) } S_{22}=\{(0,1),(0,2),(0,3),(2,0),(2,1),(2,2),(2,3)\} S 22 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 2 , 0 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 )} , S 12 = { ( 0 , 0 ) , ( 0 , 2 ) , ( 2 , 1 ) , ( 2 , 3 ) } S_{12}=\{(0,0),(0,2),(2,1),(2,3)\} S 12 = {( 0 , 0 ) , ( 0 , 2 ) , ( 2 , 1 ) , ( 2 , 3 )} .
Z 4 × Z 4 \mathbb{Z}_4\times\mathbb{Z}_4 Z 4 × Z 4 : S 11 S_{11} S 11 and S 22 S_{22} S 22 as in graph 7, S 12 = { ( 0 , 0 ) , ( 0 , 2 ) , ( 2 , 0 ) , ( 2 , 2 ) } S_{12}=\{(0,0),(0,2),(2,0),(2,2)\} S 12 = {( 0 , 0 ) , ( 0 , 2 ) , ( 2 , 0 ) , ( 2 , 2 )} .
Z 4 × Z 4 \mathbb{Z}_4\times\mathbb{Z}_4 Z 4 × Z 4 : S 11 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 2 , 0 ) , ( 3 , 0 ) } S_{11}=\{(0,1),(0,2),(0,3),(1,0),(2,0),(3,0)\} S 11 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 2 , 0 ) , ( 3 , 0 )} , S 22 = { ( 0 , 2 ) , ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 0 ) , ( 2 , 2 ) , ( 3 , 1 ) , ( 3 , 3 ) } S_{22}=\{(0,2),(1,1),(1,3),(2,0),(2,2),(3,1),(3,3)\} S 22 = {( 0 , 2 ) , ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 0 ) , ( 2 , 2 ) , ( 3 , 1 ) , ( 3 , 3 )} , S 12 = { ( 0 , 0 ) , ( 1 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) } S_{12}=\{(0,0),(1,1),(2,2),(3,3)\} S 12 = {( 0 , 0 ) , ( 1 , 1 ) , ( 2 , 2 ) , ( 3 , 3 )} .
Z 2 × Z 2 × Z 4 \mathbb{Z}_2 \times\mathbb{Z}_2 \times\mathbb{Z}_4 Z 2 × Z 2 × Z 4 : S 11 = { ( 0 , 0 , 1 ) , ( 0 , 0 , 2 ) , ( 0 , 0 , 3 ) , ( 0 , 1 , 0 ) , ( 1 , 0 , 0 ) , ( 1 , 1 , 0 ) } S_{11} = \{(0,0,1),(0,0,2),(0,0,3),(0,1,0),(1,0,0),(1,1,0)\} S 11 = {( 0 , 0 , 1 ) , ( 0 , 0 , 2 ) , ( 0 , 0 , 3 ) , ( 0 , 1 , 0 ) , ( 1 , 0 , 0 ) , ( 1 , 1 , 0 )} , S 22 = { ( 0 , 0 , 2 ) , ( 0 , 1 , 0 ) , ( 0 , 1 , 2 ) , ( 1 , 0 , 1 ) , ( 1 , 0 , 3 ) , ( 1 , 1 , 1 ) , ( 1 , 1 , 3 ) } S_{22} = \{(0,0,2),(0,1,0),(0,1,2),(1,0,1),(1,0,3),(1,1,1),(1,1,3)\} S 22 = {( 0 , 0 , 2 ) , ( 0 , 1 , 0 ) , ( 0 , 1 , 2 ) , ( 1 , 0 , 1 ) , ( 1 , 0 , 3 ) , ( 1 , 1 , 1 ) , ( 1 , 1 , 3 )} , and S 12 = { ( 0 , 0 , 0 ) , ( 0 , 1 , 2 ) , ( 1 , 0 , 3 ) , ( 1 , 1 , 1 ) } S_{12} = \{(0,0,0),(0,1,2),(1,0,3),(1,1,1)\} S 12 = {( 0 , 0 , 0 ) , ( 0 , 1 , 2 ) , ( 1 , 0 , 3 ) , ( 1 , 1 , 1 )} .
Z 2 × Z 8 \mathbb{Z}_2 \times\mathbb{Z}_8 Z 2 × Z 8 : S 11 = { ( 0 , 1 ) , ( 0 , 4 ) , ( 0 , 7 ) , ( 1 , 1 ) , ( 1 , 7 ) } S_{11} = \{(0,1),(0,4),(0,7),(1,1),(1,7)\} S 11 = {( 0 , 1 ) , ( 0 , 4 ) , ( 0 , 7 ) , ( 1 , 1 ) , ( 1 , 7 )} , S 22 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 5 ) , ( 0 , 6 ) , ( 0 , 7 ) } S_{22} = \{(0,1),(0,2),(0,3),(0,5),(0,6),(0,7)\} S 22 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 5 ) , ( 0 , 6 ) , ( 0 , 7 )} , S 12 = { ( 0 , 0 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) , ( 0 , 6 ) , ( 0 , 7 ) } S_{12} = \{(0,0),(0,2),(0,3),(0,4),(0,6),(0,7)\} S 12 = {( 0 , 0 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 4 ) , ( 0 , 6 ) , ( 0 , 7 )} .
Z 2 × Z 8 \mathbb{Z}_2 \times\mathbb{Z}_8 Z 2 × Z 8 : S 11 = { ( 0 , 2 ) , ( 0 , 4 ) , ( 0 , 6 ) , ( 1 , 2 ) , ( 1 , 6 ) } S_{11} = \{(0,2),(0,4),(0,6),(1,2),(1,6)\} S 11 = {( 0 , 2 ) , ( 0 , 4 ) , ( 0 , 6 ) , ( 1 , 2 ) , ( 1 , 6 )} , S 22 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 5 ) , ( 0 , 6 ) , ( 0 , 7 ) } S_{22} = \{(0,1),(0,2),(0,3),(0,5),(0,6),(0,7)\} S 22 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 0 , 5 ) , ( 0 , 6 ) , ( 0 , 7 )} , S 12 = { 0 } × Z 8 S_{12} = \{0\} \times\mathbb{Z}_8 S 12 = { 0 } × Z 8 .
Z 2 × Z 8 \mathbb{Z}_2 \times\mathbb{Z}_8 Z 2 × Z 8 : S 11 = { ( 0 , 2 ) , ( 0 , 4 ) , ( 0 , 6 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 1 , 6 ) } S_{11} = \{(0,2),(0,4),(0,6),(1,0),(1,2),(1,6)\} S 11 = {( 0 , 2 ) , ( 0 , 4 ) , ( 0 , 6 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 1 , 6 )} , S 22 = { 0 } × ( Z 8 ∖ { 0 } ) S_{22} = \{0\} \times(\mathbb{Z}_8 \setminus\{0\}) S 22 = { 0 } × ( Z 8 ∖ { 0 }) , S 12 = { 0 } × Z 8 S_{12} = \{0\} \times\mathbb{Z}_8 S 12 = { 0 } × Z 8 .
Z 4 × Z 4 \mathbb{Z}_4 \times\mathbb{Z}_4 Z 4 × Z 4 : S 11 = { ( 0 , 1 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 3 , 0 ) , ( 3 , 3 ) } S_{11} = \{(0,1),(0,3),(1,0),(1,1),(3,0),(3,3)\} S 11 = {( 0 , 1 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 1 , 1 ) , ( 3 , 0 ) , ( 3 , 3 )} , S 22 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 2 , 0 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 ) } S_{22} = \{(0,1),(0,2),(0,3),(2,0),(2,1),(2,2),(2,3)\} S 22 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 2 , 0 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 3 )} , S 12 = { 0 , 2 } × Z 4 S_{12} = \{0,2\} \times\mathbb{Z}_4 S 12 = { 0 , 2 } × Z 4 .
Z 4 × Z 4 \mathbb{Z}_4 \times\mathbb{Z}_4 Z 4 × Z 4 : S 11 = { ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 2 , 0 ) , ( 3 , 0 ) } S_{11} = \{(0,1),(0,2),(0,3),(1,0),(2,0),(3,0)\} S 11 = {( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) , ( 1 , 0 ) , ( 2 , 0 ) , ( 3 , 0 )} , S 22 = { ( 0 , 2 ) , ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 0 ) , ( 2 , 2 ) , ( 3 , 1 ) , ( 3 , 3 ) } S_{22} = \{(0,2),(1,1),(1,3),(2,0),(2,2),(3,1),(3,3)\} S 22 = {( 0 , 2 ) , ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 0 ) , ( 2 , 2 ) , ( 3 , 1 ) , ( 3 , 3 )} , S 12 = { ( 0 , 0 ) , ( 0 , 2 ) , ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 0 ) , ( 2 , 2 ) , ( 3 , 1 ) , ( 3 , 3 ) } S_{12} = \{(0,0),(0,2),(1,1),(1,3),(2,0),(2,2),(3,1),(3,3)\} S 12 = {( 0 , 0 ) , ( 0 , 2 ) , ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 0 ) , ( 2 , 2 ) , ( 3 , 1 ) , ( 3 , 3 )} .
Z 24 \mathbb{Z}_{24} Z 24 : S 11 = { ± 1 , ± 5 , ± 6 , ± 7 , ± 11 } S_{11} = \{\pm1,\pm5,\pm6,\pm7,\pm11\} S 11 = { ± 1 , ± 5 , ± 6 , ± 7 , ± 11 } , S 22 = { 2 , 4 , … , 22 } S_{22} = \{2,4,\ldots,22\} S 22 = { 2 , 4 , … , 22 } , S 12 = { 0 , 6 , 12 , 18 } S_{12} = \{0,6,12,18\} S 12 = { 0 , 6 , 12 , 18 } .
Several of these graphs also arise over other groups: graph 1 over Z 2 \mathbb{Z}_2 Z 2 and D 4 D_4 D 4 , graph 2 over D 6 D_6 D 6 , graph 3 over D 6 D_6 D 6 , graph 4 over Z 2 × Z 3 \mathbb{Z}_2 \times\mathbb{Z}_3 Z 2 × Z 3 and D 6 D_6 D 6 , graph 6 over Z 2 × Z 4 \mathbb{Z}_2 \times\mathbb{Z}_4 Z 2 × Z 4 , graph 12 over Z 4 × Z 4 \mathbb{Z}_4 \times\mathbb{Z}_4 Z 4 × Z 4 and Z 2 × Z 4 \mathbb{Z}_2 \times\mathbb{Z}_4 Z 2 × Z 4 , and graphs 13 and 15 over Z 2 × Z 4 \mathbb{Z}_2 \times\mathbb{Z}_4 Z 2 × Z 4 .
Further examples. The graphs of Table 3 that are not constructed in the main text are the following.
n = 24 n = 24 n = 24 : take the cube Q 3 Q_3 Q 3 and partition its vertices into the four antipodal pairs P 0 , … , P 3 P_0,\ldots,P_3 P 0 , … , P 3 . Add four sets X 0 , … , X 3 X_0,\ldots,X_3 X 0 , … , X 3 of four new vertices each, join every vertex of P b P_b P b to every vertex of X b X_b X b , and add all edges inside X 0 ∪ X 3 X_0 \cup X_3 X 0 ∪ X 3 and inside X 1 ∪ X 2 X_1 \cup X_2 X 1 ∪ X 2 , so that these two sets induce copies of K 8 K_8 K 8 . The cube vertices have degree 3 + 4 = 7 3 + 4 = 7 3 + 4 = 7 and the new vertices 2 + 7 = 9 2 + 7 = 9 2 + 7 = 9 .
n = 55 n = 55 n = 55 : take five cliques K 5 K_5 K 5 , indexed by b < 5 b < 5 b < 5 , and join the clique with index b b b completely to six new vertices ℓ b , 1 , … , ℓ b , 6 \ell_{b,1},\ldots,\ell_{b,6} ℓ b , 1 , … , ℓ b , 6 ; finally, join ℓ b , i \ell_{b,i} ℓ b , i and ℓ b ′ , i \ell_{b',i} ℓ b ′ , i whenever b ≠ b ′ b \ne b' b = b ′ . The new vertices have degree 5 + 4 = 9 5 + 4 = 9 5 + 4 = 9 and the clique vertices 4 + 6 = 10 4 + 6 = 10 4 + 6 = 10 .
n = 60 n = 60 n = 60 : for c ∈ { 0 , 1 } c \in\{0,1\} c ∈ { 0 , 1 } and g ∈ { 0 , 1 , 2 } g \in\{0,1,2\} g ∈ { 0 , 1 , 2 } take an edge L c , g L_{c,g} L c , g and a set H c , g H_{c,g} H c , g of eight vertices. Each H c = H c , 0 ∪ H c , 1 ∪ H c , 2 H_c = H_{c,0} \cup H_{c,1} \cup H_{c,2} H c = H c , 0 ∪ H c , 1 ∪ H c , 2 induces K 24 K_{24} K 24 , every vertex of L 0 , 0 ∪ L 0 , 1 ∪ L 0 , 2 L_{0,0} \cup L_{0,1} \cup L_{0,2} L 0 , 0 ∪ L 0 , 1 ∪ L 0 , 2 is adjacent to every vertex of L 1 , 0 ∪ L 1 , 1 ∪ L 1 , 2 L_{1,0} \cup L_{1,1} \cup L_{1,2} L 1 , 0 ∪ L 1 , 1 ∪ L 1 , 2 , and L c , g L_{c,g} L c , g is joined completely to H c ′ , g ′ H_{c',g'} H c ′ , g ′ whenever c ≠ c ′ c \ne c' c = c ′ and g ≠ g ′ g \ne g' g = g ′ . The vertices of the edges L c , g L_{c,g} L c , g have degree 1 + 6 + 16 = 23 1 + 6 + 16 = 23 1 + 6 + 16 = 23 and the others 23 + 4 = 27 23 + 4 = 27 23 + 4 = 27 .
n = 192 n = 192 n = 192 : take three copies C 0 , C 1 , C 2 C_0,C_1,C_2 C 0 , C 1 , C 2 of K 4 K_4 K 4 , completely joined to one another, and for each i i i join C i C_i C i completely to a copy P i P_i P i of the complete tripartite graph K 8 , 8 , 8 K_{8,8,8} K 8 , 8 , 8 , which is in turn joined completely to a copy D i D_i D i of K 36 K_{36} K 36 . The degrees are 3 + 8 + 24 = 35 3 + 8 + 24 = 35 3 + 8 + 24 = 35 on C i C_i C i , 16 + 4 + 36 = 56 16 + 4 + 36 = 56 16 + 4 + 36 = 56 on P i P_i P i and 35 + 24 = 59 35 + 24 = 59 35 + 24 = 59 on D i D_i D i . This is the blow-up of a triangle with a pendant path of length two at each vertex.
The graph on 33 vertices of Table 3 arose in a search over graphs with a two-orbit abelian group of automorphisms and is given in the ancillary files.
Data and reproducibility. The accompanying supplementary archive is organised into three directories alongside the verification scripts. The data directory provides the graph6 files examples.g6 (the sixteen graphs of Table 2 ), examples_new.g6 (the ten graphs of Table 3 ), catalogue.g6 (all 138 graphs of Section 6, with their tabulated invariants in catalogue.tsv), and examples_order10.g6 (the two ten-vertex graphs of Proposition 7.1), together with the parameter list fourparam.members.txt for the 3654 members of the family G ( s , a , k , h ) \mathcal{G}(s,a,k,h) G ( s , a , k , h ) from Appendix A. For each graph in Table 3 , the certificates directory supplies an explicit integer matrix X X X and integer c c c satisfying ( n L + J ) X = c I (nL + J)X = cI ( n L + J ) X = c I , allowing resistance-regularity to be certified by a single integer matrix multiplication. Thirteen self-contained Python 3 and C scripts (01–13), using numpy, networkx, sympy, python-flint, pynauty and nauty/geng [28 ] , verify all exact rational invariants and symbolic derivations across § 3 –§ 7 and Appendix § 9 , including the built-in geng filter and per-chunk audit for 11 ≤ n ≤ 13 11 \le n \le13 11 ≤ n ≤ 13 . Full run logs, command lines, software versions and the backward-error analysis are provided in logs/ and scripts/README.md.