## Abstract

Considerable progress has recently been made in the development of techniques to exactly determine two-point resistances in networks of various topologies. In particular, two types of method have emerged. One is based on potentials and the evaluation of eigenvalues and eigenvectors of the Laplacian matrix associated with the network or its minors. The second method is based on a recurrence relation associated with the distribution of currents in the network. Here, these methods are compared and used to determine the resistance distances between any two nodes of a network with topology of a hammock.

## 2. Introduction

The computation of *two-point resistances* in networks is a classical problem in electric circuit theory and graph theory, with applications in the study of transport in disordered media [1–3], random walks [4], first-passage processes [5] and lattice Green's functions [6]. In recent decades, and especially in recent years, the problem has received widespread interest in the mathematical, physical, engineering and chemical sciences because of its relevance to such a broad range of problems. A nice interpretation of the two-point resistance *R*_{ij} between nodes *i* and *j* in a graph was given by Klein & Randic [7] as a novel distance function, sometimes called the *resistance distance* between nodes *i* and *j*. The term was used because of the associated physical interpretation: for unit resistors on each edge of a graph, *R*_{ij} is small when there are many paths between the nodes *i* and *j*, and large when there are few paths between the nodes *i* and *j*. The total effective resistance, also called the *Kirchhoff index* [7,8], was introduced in chemistry as an improved alternative to other parameters used for distinguishing different molecules with similar shapes. Also, it has been shown that the first passage time of random walks (the expected time to pass a special node for a walker starting from a source node) is related to the *effective resistance* [4]. However, it is usually very difficult to obtain resistance distances in large complex graphs.

Different methods have recently been developed to compute the two-point resistances or resistance distances. These include using the eigenvalues and eigenvectors of the Laplacian matrix associated with the network [9–11], the eigenvalues and eigenvectors of the minors of the Laplacian matrix [12,13], the determinants of submatrices of the Laplacian matrix [14–16] and recursion relations [17–20].

Here, we compare two recently developed methods [13,17,19] by focusing on the determination of the point-to-point resistance in a rectangular resistor network with two additional nodes. Each of these nodes (denoted *O* and *O*′ in the hammock network of figure 1) is connected to all of the nodes in one of two opposing edge rows. With free boundary conditions at the two edge columns, we refer to the network as a ‘hammock’. Nodes along the *M* rows are connected by resistors of strength *r* while nodes along the *N* columns are linked by resistance *s*. The additional resistors connecting to *O* and *O*′ also have resistance *s*.

The first method presented here is based on evaluating eigenvalues and eigenvectors of the Laplacian matrix [10] or first-order [12] or second-order [13] minors of the Laplacian matrix associated with the resistor network. In what follows, we will refer to this method as the *Laplacian approach* or *method A*. The second method [19] is based on the solution of a recurrence relation obtained by a matrix transformation of the equations relating the column currents. We refer to this method as the *recursion-transform* (*R-T*) *method* or *method B*.

The paper is organized as follows. In §3, we briefly describe the two methods. In §4, we present a summary of our results for the point-to-point resistance for the ‘hammock’ network. We show how these results are obtained by *methods A* and *B* in §5. We compare the two methods in §6.

## 3. Description of the two methods

### 3.1 Method A: using Laplacians

If *J*_{i}(*k*) is the current injected (or removed if negative) into the node at the intersection of row *i* and column *k*, and if *V*_{k}(*i*) is the corresponding potential, then, at interior nodes, current conservation gives
*J*_{0} is the current at the added node *O* and if *J*_{M+1} is the current at added node *O*′, and if these have potentials *V*_{0} and *V*_{M+1}, respectively,
*T* nodes and resistance *r*_{i,j}=*r*_{j,i} between nodes *i* and *j*, thus
**L**_{T} has general element
*α* and *β* (*R*_{α,β}) can be written as [10]
_{i} are the non-zero eigenvalues of **L**_{T} and **Ψ**_{i}=(*ψ*_{i,1},*ψ*_{i,2},…,*ψ*_{i,T−1}) are the corresponding orthonormal eigenvectors.

The two-dimensional Laplacian of an *M*×*N* rectangular network with free boundaries can be written in terms of two one-dimensional Laplacians in the form
*M*-node chain with free boundaries and *U*_{M} is a unit matrix of dimension *M*. The Laplacian for other combinations of boundary conditions can be similarly written. The eigenvalues of the two-dimensional lattice matrix are therefore sums of the eigenvalues of the one-dimensional chain matrices and the eigenvectors are products of the corresponding eigenvectors.

The ‘hammock’ Laplacian cannot be decomposed in this way, so that the eigenvalues and eigenvectors are far more difficult to determine. A similar problem arises if only one additional vertex is added to the rectangle, giving rise to a ‘fan’ network [21]. However, for the ‘fan’ only *MN* of the *MN*+1 equations (3.3) are independent so setting the potential of the extra vertex to zero eliminates the corresponding row and column and the Laplacian may be replaced by the resulting minor which may be decomposed in the form (3.6). The resulting equations are independent and all of the eigenvalues are non-zero and are to be included in the sum (3.5). This method is due to Izmailian, Kenna and Wu who used it to determine the ‘cobweb’ [12] and ‘fan’ [21] resistance.

If the free boundary conditions of the ‘hammock’ are replaced by periodic ones, the resulting topology is known as a ‘globe’. The same problem arises in that the Laplacian cannot be decomposed. Izmailian & Kenna [13] showed that a solution was to replace the Laplacian by the minor *α* and *β* other than the node 0 is

### 3.2 Method B

*Method B* was introduced by Tan [17]. See also Tan *et al.* [18]. Let *I*_{k}(*i*) be the upward current in column *k* between nodes at heights *i*−1 and *i*. We consider the ‘hammock’ to be a rectangle with *N* columns and *M*+2 rows with zero resistance in the top and bottom rows. The rows are labelled *i*=0 to *M*+1 (figure 2).

Suppose current *J* is injected in column *k*=*z* at height *i*=*y*. In §5.2, we derive the following relation between the currents in three adjacent columns:
*i* have resistance *r*_{i}. For the ‘hammock’ *r*_{0}=*r*_{M+1}=0 and *r*_{i}=*r* for 1≤*i*≤*M*.

With the definition *I*_{k}={*I*_{k}(1),*I*_{k}(2),…,*I*_{k}(*M*+1)}^{T}, the current terms involving the radial resistance on the right of equation (3.8) may be expressed in matrix form as *r***L**^{free}_{M+1}*I*_{k}, where **L**^{free}_{M+1}≡2*U*_{M+1}−*W*_{M+1} is the Laplacian matrix for a linear chain of *M*+1 nodes with free boundaries. Here, *W*_{M+1} is given by equation (5.39).

The eigenvalues and eigenvectors of **L**^{free}_{m} are known [10]. Next, we define a matrix ** Ψ**, the rows of which are the eigenvectors of

**L**

^{free}

_{M+1}, and use it to obtain transformed current vectors

*X*

_{k}≡

**Ψ**I_{k},

*k*=1,2,…,

*N*. Applying

**to the matrix form (5.37) of equation (3.8) shows that for each row**

*Ψ**i*,

*X*

_{k}(

*i*) satisfies a separate second-order recurrence on the column index

*k*(see (5.46)). This may be solved in the standard way with two parameters in each of the three regions of

*k*delineated by the boundaries and the input and output nodes. Having determined the parameters by imposing the boundary conditions, the currents are obtained from the resulting

*X*

_{k}using the inverse transformation

*I*

_{k}=

*Ψ*^{−1}

*X*

_{k}. The potential difference, and hence the resistance, between the input and output nodes is obtained by summing the potential differences (determined by the currents) along a path between the nodes via the common node

*i*=

*M*+1 (see equation (5.33)).

## 4. Results for the resistance of the *M*×*N* ‘hammock’ network between two arbitrary nodes

We next present some new results for the ‘hammock’ network coming from each approach. Then we present details of the derivations using each method. In the final section, we compare the advantages and disadvantages of each approach.

### 4.1 Notation

*Method A*. The nodes of the rectangular part of the ‘hammock’ are labelled by (*x*,*y*), where *x*=1,2,…,*N* and *y*=1,2,…,*M*. The input and output nodes are *α*=(*x*_{1},*y*_{1}) and *β*=(*x*_{2},*y*_{2}), respectively.

*Method B*. The ‘hammock’ will be supposed to have *N*=*s*+*t*+1 radial lines, labelled from *k*=−*s* to *k*=*t*. The input node *N*_{p}≡*α* is distant *y*_{1} up the radial line *k*=−*p* and the output node *N*_{q}≡*β* is distant *y*_{2} up the radial line *k*=*q*. Thus *x*_{1}=*s*−*p*+1=*N*−*t*−*p* and *x*_{2}=*s*+*q*+1=*N*+*q*−*t* (figure 2).

### 4.2 Main result

Let _{i} be the greater solution of
*h*=*r*/*s* the horizontal-to-vertical resistance ratio. With
*N*_{p} and *N*_{q} is found to be

### 4.3 Resistance between two nodes on the same radial line

Without loss of generality, we take the line to be *k*=0 and set *p*=*q*=0 so that *x*_{1}=*x*_{2}=*x*. In this case, *α*=*β*=*γ* with the result
*s*+1=2*x*_{1}−1 and 2*t*+1=2*N*−2*x*_{2}+1.

### 4.4 Resistance between two nodes on the same transverse line

Setting *y*_{1}=*y*_{2}=*y*, so that *S*_{i}(*y*_{1})=*S*_{i}(*y*_{2})=*S*_{i}(*y*), the numerator of the summand in (4.3) becomes (*α*−2*β*+*γ*)*S*_{i}(*y*)^{2}. Further, if we set *p*=*q*, the distance between the input and output nodes is *d*=2*q*=*x*_{2}−*x*_{1}. In this case,
*s*=*t*, then the input and output nodes are symmetrically placed relative to the radial line boundaries and

## 5. Derivation of the general form (4.3) by two different methods

### 5.1 Method A: using the Laplacian approach [13]

We begin with the expression (3.7) for the point-to-point resistance in terms of the Laplacian *x*,*y*),*x*=1,2,…,*N*,*y*=1,2,…,*M*} so that in (3.7), *i*=*x*+(*y*−1)*N* (figure 3). Node (1,1) is positioned at the lower left-hand corner. For the ‘hammock’ network, the elements of the first row and column of the Laplacian (3.4) have the following values:
*c*_{0} is given by
*i*,*j*)th element of the inverse matrix *Λ*_{k} and *ψ*_{k,i} are eigenvalues and eigenvectors of the second minor

The second minor of the Laplacian for the ‘hammock’ network may be factored in a similar way to the rectangular network. For the example of figure 4

The eigenvalues and eigenvectors of *u*_{n}(*x*),*n*=0,1,…,*N*−1 are the eigenvectors of *v*_{m}(*y*), *m*=0,1,…,*M*−1 are the eigenvectors of *θ*_{n}=*πn*/*N* and *φ*_{m}=*π*(*m*+1)/(2*M*+2).

The eigenvectors are orthogonal so
*v*_{m}(*y*). The inverse Laplacian (5.5) may now be written

#### 5.1.1 Evaluating the sums *Σ*_{1} and *Σ*_{2}

Let us now calculate the two sums in (5.3). We need
*i*=1 to *N* is equivalent to the sum *x*=1 to *N* with *y*=1, we start by evaluating
*y*' in the range *y*′≤2*M*+1, which is clearly our case. The two required sums now follow:
*α*=(*x*_{1},*y*_{1}) and the output node *β*=(*x*_{2},*y*_{2}) and we have used (5.14).

Substituting *Σ*_{1} and *Σ*_{2} into equation (5.2), the required resistance now takes the form

#### 5.1.2 Evaluating R ^ x 1 , y 1 x 2 , y 2

We must first evaluate *n*=0 would need to be treated separately. However, note that *u*_{N}(*x*)=0 and for *n*=1 to *N*−1, *u*_{2N−n}(*x*)=−*u*_{n}(*x*) and *Λ*_{m,2N−n}=*Λ*_{m,n} so
*n*=1 to 2*N*−1 let *w*_{0}(*x*)=*u*_{0}(*x*) so
*n*=0 term is no longer special. Now, for integer ℓ, we have the identity [10], eqn (62)
*Ω*_{m}) by
*x*′≥*x*. Note that the identity (5.25) has enabled the double sum (5.24) to be reduced to a single sum.

From (5.4)
*Ω*_{m}=*L*_{m+2}. Note also that *x*_{2}≥*x*_{1} and combining (5.21), (5.31) and (5.32) gives (4.3).

### 5.2 Method B: using the recursion-transform technique of Tan [17]

We use the *k*,*s*,*t*,*p*,*q* notation defined in §4. This choice enables the use of symmetry and produces more symmetric coefficients (4.5).

Suppose that current *J* is input at *N*_{p} and flows out at *N*_{q}. Let *I*_{k}(*i*) be the resulting radial current in the *i*th resistor from the lower edge of column *k* in the direction of increasing *i* (figure 5). Using Ohm's law, the potential difference between *N*_{p} and *N*_{q} may be measured along a path from *N*_{q} to the common node *i*=*M*+1 and then to *N*_{p} with the result

#### 5.2.1 Relating the current distribution in three adjacent radial lines

To determine the radial currents consider the voltage loop *ABEFCBEDA*, shown in figure 5, centred on the *i*th resistor of the *k*th radial line. If current *J* enters at the node of height *y* on the radial line *k*=*z* charge conservation gives
*z*=*q* or −*p* and *y*=*y*_{1} or *y*_{2}. When *i*=1 in (5.34), *I*_{k}(*i*−1)=0. The sum of the voltage differences round the loop is zero so using Ohm's law
*r*_{i}=*r* for 1≤*i*≤*M*, *r*_{0}=*r*_{M+1}=0. Combining these equations
*h*_{i}=*r*_{i}/*s*. With *h*=*r*/*s*, equation (5.37) may be written in matrix form
*U*_{m} is an *m*-dimensional unit matrix, *ϵ*_{y} is a column matrix with *i*th element *ϵ*_{i,y}=*δ*_{i,y+1}−*δ*_{i,y} and

For *k*=*t*, we only use the loop *ABEDA* in figure 5 to obtain the boundary equations
*k*=−*s*.

#### 5.2.2 The recurrence relation

Let *χ*_{i}≡*φ*_{i−2}=(*i*−1)*π*/(2*M*+2). *W*_{M+1} has eigenvalues *ψ*_{i},*i*=1,2,…,*M*+1. The *j*th component of *ψ*_{i} is given by [10]
** Ψ** be the matrix with

*i*th row

*ψ*

_{i}and define

*X*

_{k}=

**Ψ**I_{k}.

**is invertible with general element of the inverse**

*Ψ**i*>1

*s*

_{1}(

*y*)=(

*M*+1−

*y*)/(

*M*+1).

Multiplying (5.41) on the left by ** Ψ**, noting that

**Ψ**W_{M+1}is diagonal with diagonal elements

*w*

_{i}, and taking the

*i*th component

*u*

_{i}=2

*h*+2−

*hw*

_{i}and

**to (5.41) and taking the**

*Ψ**i*th component

#### 5.2.3 Solving the recurrence relation

For *k*≠*z*, the general solution of (5.46) is a linear combination of _{i} and *k*=*q* and *k*=−*p*,
*k*=*q* and *k*=−*p* radial lines where the current *J* is input and output. Using (5.46) with *k*=*z*=*q* and secondly with *k*=*z*=−*p*, in the second case replacing *J* by −*J*
*A*_{i} and *i*≤*M*+1
*χ*_{1}=0 and λ_{1}=1 so the above expressions are indeterminate when *i*=1, but this may be resolved by taking limits.

## 6. Summary and discussion

We have derived the resistance between two arbitrary nodes of the ‘hammock’ network using the two different methods, A and B.

Instead of focusing on the potentials as in the Laplacian approach of method A, the recursive strategy in method B is to obtain a relation between the vertical currents in three adjacent columns.

Besides different starting strategies, we use different coordinate notations for the different approaches. The coordinates used in method B enable the use of symmetry and lead to symmetric coefficients (4.5).

Each approach has its advantages and disadvantages in general. For method A, the formula (3.5) for the two-point resistance is valid for an arbitrary network. The two-point resistance can be computed for cubic lattices in any spatial dimension (as the Laplacian for *d*-dimensional regular square lattices can be represented as the sum of *d* one-dimensional Laplacians, with known eigenvalues and eigenvectors) under various boundary conditions [10], for example free or periodic. Thus the resistance problem is one of the few non-trivial problems which can be solved exactly in high dimensions. Once the eigenvalues and eigenvectors of the Laplacian are known, the resistance between two arbitrary points is given by a very simple summation formula (3.5). While the determination of the eigensystem is straightforward to obtain for hypercubic lattices in any dimensions, the approach cannot readily deal with other complex graphs. However, for the square lattice with one or two added nodes, the Laplacian may be replaced by its first or second minors, respectively, for example, as in method A.

In terms of applications to the ‘hammock’ network, conversion to a rectangular network is an essential part of both methods. In method A, this is so that the decomposition (3.6) may be used. In method B, the ‘hammock’ is extended to a full rectangle with *N* columns and *M*+2 rows with zero resistance in the top and bottom rows. If *r*_{i} is the value of the resistors in row *i* of the rectangle, then *r*_{0}=*r*_{M+1}=0 and otherwise *r*_{i}=*r* so that the same recursion (5.37) can be used for all rows. This extension is not possible in method A as the coefficients are conductances and would be infinite in the top and bottom rows. Instead, the contribution of the two additional nodes is first separated to yield (3.7).

Both methods use the eigenvectors and eigenvalues of the Laplacian **L**^{free}_{m} of the linear chain of length *m* with free boundaries. Method A further requires the eigensystem for the Laplacian of a chain with Dirichlet–Dirichelet boundary conditions. This leads to a double sum (5.24) and in order to arrive at the final formula one of the sums has to be removed using a non-trivial identity (5.25). Reference is made to Wu [10] for the proof of the identity. The summation which occurs in the final formula is the starting point of method B (5.33) and the summand involves the transformed current vector and the inverse of the eigenvector matrix (see (5.44)). The former requires the solution of a recurrence relation with constant coefficients and the latter involves a trivial summation (5.45). Finally, method A requires reference to previous calculations (3.7) and (5.25), whereas method B is virtually self-contained using only Ohm's law and Kirchhoff's laws.

The Laplacian approach of method A has so far delivered analytical formulae for the two-point resistances for classes of graphs such as regular two-dimensional square lattices under different boundary conditions [10]; higher dimensional regular square lattices [10]; regular square lattices with a single additional node; so-called cobweb [12] and fan [21] networks; and regular square lattices with two additional nodes—the so-called globe network [13].

Method B has previously been applied to the fan [22], cobweb [23] and globe networks [19]. The method has also been used on the regular square lattice but the potential difference along the top edge is non-zero and has to be calculated by interchanging the *x*- and *y*-axes; alternatively, the required potential difference may be determined along a vertical path followed by a horizontal path (J.W. Essam 2014, unpublished data).

Method B could also be applied to problems where the horizontal resistance depends in different ways on the row index *i*. The simplest of these would be *r*_{i}=*ir* which would apply to a fan network embedded in the plane where the length of the resistor wires would be proportional to the distance from the apex. The method as presented here would then require finding the eigensystem of a tridiagonal matrix with elements depending on *r*_{i}. This can be avoided by working with the vector *I*(*i*)≡{*I*_{1}(*i*),*I*_{2}(*i*),…,*I*_{N}(*i*)} which when transformed would lead to a second-order recurrence relation with coefficients depending on *i*.

## Funding statement

This work was supported by a Marie Curie IIF (project no. 300206-RAVEN) and IRSES (project nos. 295302-SPIDER and 612707-DIONICOS) within 7th European Community Framework Programme and by a grant of the Science Committee of the Ministry of Science and Education of the Republic of Armenia under contract 13-1C080.

## Authors' contributions

R.K. and N.I. wrote the account of the Laplacian matrix approach (method A) and implemented it for the hammock network. J.E. and Z.T. wrote the account of the recursion-transform approach (method B) and implemented it for the hammock network. All authors contributed to drafting the manuscript, read and approved the manuscript before submission and all authors gave final approval for publication.

## Conflict of interests

We have no competing interests.

- Received November 3, 2014.
- Accepted March 31, 2015.

© 2015 The Authors. Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/, which permits unrestricted use, provided the original author and source are credited.