Resistors in dual networks

Martina Furrer^a , Norbert Hungerbuhler ¨ b , Simon Jantschgi^c

^aBerufsbildungszentrum des Kantons Schaffhausen, 8200 Schaffhausen, Switzerland

martina.furrer@bbz-sh.ch, norbert.hungerbuehler@math.ethz.ch, simon.jantschgi@uzh.ch

Let G be a finite plane multigraph and G⁰ its dual. Each edge e of G is interpreted as a resistor of resistance Re, and the dual edge e 0 is assigned the dual resistance R^{e 0} := 1/Re. Then the equivalent resistance r^e over e and the equivalent resistance r^{e 0} over e 0 satisfy re/R^e +r^{e 0}/R^{e 0} = 1. We provide a graph theoretic proof of this relation by expressing the resistances in terms of sums of weights of spanning trees in G and G⁰ respectively.

Keywords: dual graphs, electrical networks, equivalent resistance Mathematics Subject Classification: 05C05, 05C12, 15A15, 15A18

DOI: 10.5614/ejgta.2020.8.2.6

1. Introduction

The systematic study of electrical resistor networks goes back to the German physicist Gustav Robert Kirchhoff in the middle of the 19th century. In particular, Kirchhoff's node and loop laws, and Ohm's law allow to fully describe the electric current and potential in a given static network of resistors and voltage sources. In the course of his investigations, Kirchhoff discovered the Matrix Tree Theorem, which states that the number of spanning trees in a graph G is equal to any cofactor of the Laplacian matrix of G. Surprisingly, this purely graph theoretic fact has a deep connection to the physical question of the equivalent resistance between two vertices of an electric network.

In the simplest situation, a finite simple graph G can be interpreted as an electrical network by considering each edge as a resistor of 1 Ohm. One is then interested in the resulting equivalent

Received: 5 August 2018, Revised: 7 May 2020, Accepted: 24 May 2020.

^bDepartment of Mathematics, ETH Zurich, 8092 Z ¨ urich, Switzerland ¨

^cUniversity of Zurich, 8050 Zurich, Switzerland ¨

resistance between any two vertices. For example, a method developed by Van Steenwijk [8] has recently been generalized to calculate the resistance between any two vertices of a symmetrical polytope (see [6]). For general graphs the key observation for solving the problem goes back to Kirchhoff: The equivalent resistance over an edge e in the graph G is given by the quotient of the number of spanning trees containing the edge e divided by the total number of spanning trees in G.

More generally, we may consider a finite multigraph G and assign to each edge e of G a weight R^e > 0 interpreted as resistance of e. Also in this case, the equivalent resistance between two vertices can be expressed in terms of sums of weights of spanning trees (see Section 2).

Consider a cube as a graph with unit resistance on each edge and the dual polyhedron, the octahedron, in the same way. The equivalent resistance over an edge of the cube turns out to be 7/12 Ohm, the equivalent resistance over an edge of the octahedron is 5/12 Ohm. Observe, that these values add up to 1! The same phenomenon occurs for the dodecahedron with equivalent resistance of 19/30 Ohm over each edge and the dual graph, the icosahedron, with 11/30 Ohm, or the rhombic dodecahedron with equivalent resistance of 13/24 Ohm over each edge and the dual graph, the cuboctahedron, with 11/24 Ohm. This is not just a coincidence: Suppose that a planar graph and its dual are both interpreted as electrical networks with unit resistance for all edges. Now, if r^e is the equivalent resistance over an edge e and r 0 e is the equivalent resistance over the dual edge e 0 , then r^e +r 0 ^e = 1 (see [2, Exercise 7, Section 10.5], [9, Theorem 2.3]). The aim of this article is to generalize this formula to plane networks with arbitrary resistors (see Theorem 5) and to give a graph theoretic proof.

2. Preliminaries

Let G be a finite connected graph with n ≥ 3 vertices and without loops. Multiple edges are allowed. Each edge e is considered as a resistor of resistance R^e > 0. Then, we consider the weighted Laplace matrix L = (`ij ) of G defined as

\[\ell_{ij} := \begin{cases} -\sum\frac{1}{R_e}, & \text{where the sum runs over all edges } e \ & \text{between the vertices } i \text{ and } j^1, \ a_{ii}, & \text{if } i=j, \end{cases}\]

where the diagonal values aii are chosen such that the sum of all rows of L vanishes. The weight of a subgraph H of G is defined as

\[\Pi(H) := \prod_{e \text{ an edge of } H} \frac{1}{R_e} \,.\]

The set of all spanning trees of a graph G will be denoted by S(G). We recall the following:

¹By convention, an empty sum is 0.

Proposition 1. (i) The value of each cofactor \(L_{ij}\) of L is the sum of the weights of all spanning trees of G.

(ii) Let \(L_{ij,ij}\) denote the determinant of the matrix L with rows i, j and columns i, j deleted, and let e be an edge between the vertices i and j. Then the quotient \(L_{ij,ij}/R_e\) equals the sum of the weights of all spanning trees of G which contain the edge e.

Proof. The first part of the proposition follows directly from a general version of the Matrix Tree Theorem (see, e.g., [7, Theorem VI.27]).

For the second part we proceed as follows: Observe, that by using the edge e between the vertices i and j we can split up the sum of the weights of all spanning trees of G as follows:

\[\sum_{T \in S(G)} \Pi(T) = \sum_{\substack{T \in S(G) \\ e \in T}} \Pi(T) + \sum_{\substack{T \in S(G) \\ e \notin T}} \Pi(T). \tag{1}\]

Furthermore, the second sum on the right-hand side of (1) corresponds to the sum of the weights of all spanning trees of G - e, i.e., G with edge e removed. Using the first part of the proposition, we get from (1) that

\[\sum_{\substack{T \in S(G) \\ e \in T}} \Pi(T) = L_{ii} - L_{ii}^e,\]

where \(L^e = (\ell_{hk}^e)\) is the weighted Laplace matrix of G - e. We have

\[\ell_{ij}^e = \ell_{ji}^e = \ell_{ij} + \frac{1}{R_e}, \quad \ell_{ii}^e = \ell_{ii} - \frac{1}{R_e}, \quad \ell_{jj}^e = \ell_{jj} - \frac{1}{R_e}\]

and \(\ell_{hk}^e = \ell_{hk}\) for all other h, k. The term \(L_{ii} - L_{ii}^e\) can be computed using Laplace's cofactor expansion. Expanding both \(L_{ii}\) and \(L_{ii}^e\) along the j-th row yields

\[\sum_{T \in S(G) \atop e \in T} \Pi(T) = \sum_{k \neq i} \ell_{jk} (L_{ii})_{jk} - \sum_{k \neq i} \ell_{jk}^e (L_{ii}^e)_{jk}.\]

Since the cofactors \((L_{ii})_{jk}\) and \((L_{ii}^e)_{jk}\) are equal for all k we are left with

\[\sum_{T \in S(G) \atop e \in T} \Pi(T) = (\ell_{jj} - \ell_{jj}^e)(L_{ii})_{jj} = \frac{L_{ij,ij}}{R_e}.\]

Remark. The second part of Proposition 1 follows also quite easily from the All Minors Matrix Tree Theorem (see [4]).

The connection to the equivalent resistance is given by the following

Proposition 2. Let e be an edge between the vertices i and j. Then the equivalent resistance \(r_e\) over the edge e is given by

\[r_e = \frac{L_{ij,ij}}{L_{11}} \,. {2}\]

Remark. Recall, that by Proposition 1(i) the denominator in (2) can be replaced by any other cofactor \(L_{hk}\).

Proof. Observe that the Laplace matrix of the weighted multigraph G corresponds to the Laplace matrix of a weighted simple graph H where the multiple edges \(e_1, \ldots e_k\) between each two vertices i and j of G are collapsed to a single edge e with weight

\[R_e = \frac{1}{\frac{1}{R_{e_1}} + \ldots + \frac{1}{R_{e_k}}}.\]

However this value corresponds exactly to the equivalent resistance of the parallel resistors \(R_{e_1}, \ldots, R_{e_k}\). Thus, the equivalent resistance over the vertices i and j in G equals the equivalent resistance over the vertices i and j in H and the claim follows from [1, Remark 2.1, Equation (16)] for simple graphs, and Proposition 1.

From now on we assume that G is a finite planar multigraph with dual graph G'. Recall that in general G' depends on the embedding of G in the plane.

Definition 3. Let G' be the dual of a planar embedded multigraph G, and let G be interpreted as an electrical network by associating to each edge e a resistance \(R_e > 0\). For each edge e of G, we define the electrical resistance \(R_{e'}\) of the dual edge e' to be the conductance of e, i.e., \(R_{e'} := 1/R_e\). Then, G' equipped with these resistances is called the dual electrical network of G.

Observe that the Laplace matrix \(L' = (\ell'_{ij})\) of the dual electrical network G' is given by

\[\ell'_{ij} := \begin{cases} -\sum \frac{1}{R_{e'}} = -\sum R_e, & \text{where the sum runs over all edges } e' \\ & \text{between the vertices } i \text{ and } j \text{ of } G', \\ a_{ii}, & \text{if } i = j, \end{cases}\]

where the diagonal values \(a_{ii}\) are chosen such that the sum of all rows of L' vanishes. Similarly the weight of a subgraph H' of G' is

\[\Pi(H') := \prod_{e' \text{ an edge of } H'} \frac{1}{R_{e'}} = \prod_{e' \text{ an edge of } H'} R_e \,.\]

Then we have:

Proposition 4. (i) The value of an arbitrary cofactor \(L'_{ij}\) of L' is equal to the sum of the weights of all spanning trees in G' and therefore

\[L'_{ij} = L_{ij}\Pi(G'),\tag{3}\]

where \(\Pi(G') = \prod R_e\) is the total weight of G'.

(ii) The product \(R_e L'_{ij,ij}\) equals the sum of the weights of the spanning trees in G' which contain the dual edge e' of edge e.

Proof. We only have to show equation (3), since all other statements follow from Proposition 1. Let Ψ denote the canonical bijection from S(G⁰ ) to S(G) given by Ψ(T 0 ) = {e ∈ G|e ⁰ ∈ G⁰ −T 0}. Observe that the weight of a spanning tree T ⁰ of G⁰ can be expressed as

\[\Pi(T') = \frac{\Pi(G')}{\Pi(G' - T')}.\] (4)

Using the bijection Ψ and Definition 3 in (4), namely the fact, that the electrical resistance of an edge in G⁰ is equal to the conductance of the dual edge in G, we get

\[\Pi(T') = \Pi(G')\Pi(\Psi(T')). \tag{5}\]

The characterization of Lij and L 0 ij as the sum of the weights of all spanning trees of G and G⁰ respectively leads, together with (5), to

\[L'_{ij} = \sum_{T' \in S(G')} \Pi(T') = \sum_{T' \in S(G')} \Pi(G') \Pi(\Psi(T')) =\] \[= \Pi(G') \sum_{T \in S(G)} \Pi(T) = \Pi(G') L_{ij},\]

where we have used the bijectivity of Ψ in the penultimate equality. This completes the proof.

3. The sum formula in dual networks

The main result is now the following:

Theorem 5. Let R^e be the resistance of an edge e and R^{e 0} = 1/R^e the resistance of the dual edge e 0 in the dual electrical network. Let r^e denote the equivalent resistance over edge e and r^{e 0} denote the equivalent resistance over edge e 0 . Then

\[\frac{r_e}{R_e} + \frac{r_{e'}}{R_{e'}} = 1.\]

For a proof of this formula based upon physical arguments see [5]. Here, we provide a purely graph theoretic proof.

Proof. Let e be an edge between the vertices i and j in G, and we may assume that the vertices are numbered such that e 0 also runs between the vertices i and j in G⁰ . In a first step, we are going to derive a new expression for L 0 ij,ij . Let Ψ be the canonical bijection from S(G⁰ ) to S(G) as defined in the proof of Proposition 4. By part (ii) of Proposition 4 we have

\[L'_{ij,ij} = \frac{1}{R_e} \sum_{\substack{T' \in S(G') \\ e' \in T'}} \Pi(T').\] (6)

The identity (5) and the fact that \(\Psi(T')\) does not contain the edge e if T' contains the dual edge e' allow to rewrite the right-hand side of (6) as follows

\[\frac{1}{R_e} \sum_{\substack{T' \in S(G') \\ e' \in T'}} \Pi(T') = \frac{\Pi(G')}{R_e} \sum_{\substack{T \in S(G) \\ e \notin T}} \Pi(T).\] (7)

Furthermore, the sum on the right-hand side of (7) can be expressed as the difference between the sum of the weights of all spanning trees of G and the sum of the weights of the spanning trees that contain the edge e. Therefore, it holds that

\[L'_{ij,ij} = \frac{\Pi(G')}{R_e} \Big( \sum_{T \in S(G)} \Pi(T) - \sum_{T \in S(G) \atop a \in T} \Pi(T) \Big).\] (8)

Using Proposition 1 in (8) yields the following identity:

\[L'_{ij,ij} = \frac{\Pi(G')}{R_e} \left( L_{ii} - \frac{L_{ij,ij}}{R_e} \right). \tag{9}\]

Now, in a second step, it follows from Proposition 2 and Definition 3, that

\[\frac{r_e}{R_e} + \frac{r_{e'}}{R_{e'}} = \frac{L_{ij,ij}}{L_{ii}R_e} + R_e \frac{L'_{ij,ij}}{L'_{ii}}.\] (10)

Using the first part of Proposition 4 and (9), we can rewrite the right-hand side of (10) and simplify the resulting expression to arrive at

\[\frac{r_e}{R_e} + \frac{r_{e'}}{R_{e'}} = \frac{L_{ij,ij}}{L_{ii}R_e} + R_e \frac{\Pi(G')}{R_e} (L_{ii} - \frac{L_{ij,ij}}{R_e}) = 1,\]

as claimed. \(\Box\)

Example 6. Let us consider the following electrical network:

The corresponding Laplace matrix L is

\[L = \begin{pmatrix} \frac{1}{R_1} + \frac{1}{R_2} & -\frac{1}{R_2} & 0 & -\frac{1}{R_1} \\ -\frac{1}{R_2} & \frac{1}{R_2} + \frac{1}{R_3} & -\frac{1}{R_3} & 0 \\ 0 & -\frac{1}{R_3} & \frac{1}{R_3} + \frac{1}{R_4} + \frac{1}{R_5} & -\frac{1}{R_4} - \frac{1}{R_5} \\ -\frac{1}{R_1} & 0 & -\frac{1}{R_4} - \frac{1}{R_5} & \frac{1}{R_1} + \frac{1}{R_4} + \frac{1}{R_5} \end{pmatrix}\]

The cofactor

\[L_{11} = \frac{1}{R_1 R_2 R_3 R_4 R_5} \left( R_4 (R_1 + R_2 + R_3) + R_5 (R_1 + R_2 + R_3 + R_4) \right)\]

corresponds indeed to the total weight of all spanning trees of G as one easily checks directly. For the edge e between the vertices 3 and 4 with resistance R4, we get

\[L_{34,34} = \frac{1}{R_1 R_2} + \frac{1}{R_1 R_3} + \frac{1}{R_2 R_3}\]

which, divided by R4, gives the sum of the weights of the spanning trees which contain e, as stated in Proposition 1.

The dual network looks as follows:

and the corresponding Laplace matrix is

\[L' = \begin{pmatrix} R_1 + R_2 + R_3 + R_4 & -R_4 & -(R_1 + R_2 + R_3) \\ -R_4 & R_4 + R_5 & -R_5 \\ -(R_1 + R_2 + R_3) & -R_5 & R_1 + R_2 + R_3 + R_5 \end{pmatrix}.\]

The cofactor

\[L'_{11} = R_4(R_1 + R_2 + R_3) + R_5(R_1 + R_2 + R_3 + R_4)\]

is the total weight of the spanning trees of G⁰ . And indeed, we have

\[L_{11}' = L_{11}R_1R_2R_3R_4R_5\]

as predicted by Proposition 4. Furthermore, we get

\[L'_{12,12} = R_1 + R_2 + R_3 + R_5\]

which gives according to Proposition 1, after multiplication by R4, the total weight of the trees in G⁰ which contain the dual edge e 0 .

Now, the equivalent resistances over edge e and e 0 respectively are, according to Proposition 2,

\[r_4 = \frac{L_{34,34}}{L_{11}} = \frac{R_4 R_5 (R_1 + R_2 + R_3)}{R_4 (R_1 + R_2 + R_3) + R_5 (R_1 + R_2 + R_3 + R_4)}\] \[r_4' = \frac{L'_{12,12}}{L'_{11}} = \frac{R_1 + R_2 + R_3 + R_5}{R_4 (R_1 + R_2 + R_3) + R_5 (R_1 + R_2 + R_3 + R_4)}\]

and finally indeed, with R^{0 4} = 1/R4,

\[\frac{r_4}{R_4} + \frac{r_4'}{R_4'} = 1.\]

Open Problems

It would be interesting to investigate graphs which are embedded in a compact surface of positive genus and their respective duals. In particular the results in [3] might help to generalize Theorem 5 for such graphs. However, the direct analogue is false, so one would have to expect some sort of a correction term in the formula.

Another interesting question would be to ask if Theorem 5 holds for infinite periodic planar graphs and their duals.

Acknowledgement

We would like to thank the referees for their valuable remarks and suggestions which greatly helped to improve this article.

References

• [1] P. Ali, F. Atik, and R.B. Bapat, Identities for minors of the Laplacian, resistance and distance matrices of graphs with arbitrary weights, Linear Multilinear Algebra 68 (2) (2020), 323– 336.
• [2] R.B. Bapat, Graphs and Matrices, Universitext. Springer, London; Hindustan Book Agency, New Delhi, second edition, 2014.
• [3] N. Biggs, Spanning trees of dual graphs, J. Combin. Theory Ser. B 11 (1971), 127–131.
• [4] S. Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods 3 (3) (1982), 319–329.
• [5] M. Furrer, Widerstandssumme in dualen Netzwerken, Mentorierte Arbeit, 2017, ETH Zurich. ¨
• [6] J. Moody and P.K. Aravind, Resistor networks based on symmetrical polytopes, Electron. J. Graph Theory Appl. 3 (1) (2015), 56–69.

• [7] W.T. Tutte, Graph theory, volume 21 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2001, With a foreword by Crispin St. J. A. Nash-Williams, Reprint of the 1984 original.
• [8] F.J. van Steenwijk, Equivalent resistors of polyhedral resistive structures, American Journal of Physics 66 (1) (1998), 90–91.
• [9] Y.J. Yang, An identity on resistance distances, In Material and Manufacturing Technology IV, volume 748 of Advanced Materials Research, pages 1024–1027. Trans Tech Publications, 10, 2013.