RESISTANCE DISTANCE IN GRAPHS

R.B. Bapat^{1}

1 Introduction

We consider simple graphs, that is, graphs which have no loops or parallel edges. Thus a graph G = (V (G), E(G)) consists of a finite set of vertices, V (G), and a set of edges, E(G), each of whose elements is a pair of distinct vertices. We generally take V (G) = \{1, 2, …, n\} and E(G) = \{\overline{1}, \overline{2}, …, \overline{m}\} unless stated otherwise. We will assume familiarity with basic graph-theoretic notions, see, for example, Bondy and Murty [10].

Given a graph, one associates a variety of matrices with the graph. Some of the important ones will be defined now. The adjacency matrix A(G) of G is an n × n matrix with its rows and columns indexed by V (G) and with the (i, j)-entry equal to 1 if vertices i, j are adjacent (i.e., joined by an edge) and 0 otherwise. Thus A(G) is a symmetric matrix with its i-th row (or column) sum equal to d_{i}(G), which by definition is the degree of the vertex i, i = 1, 2, …, n. Let D(G) denote the n × n diagonal matrix, whose i-th diagonal entry is d_{i}(G), i = 1, 2, …, n. The Laplacian matrix of G, denoted by L(G), is defined as L(G) = D(G) − A(G).

There is another way to define the Laplacian matrix. We first introduce another important matrix associated with a graph. Suppose each edge of G is assigned an orientation, making it into a directed graph. The (vertex-edge) incidence matrix of G, denoted by Q(G), is the n×m matrix defined as follows.

1Text of the Fourth Ganesh Prasad Memorial Award Lecture delivered at the 65th Annual Conference of the Indian Mathematical Society held at A.P.S. University, Rewa, Madhya Pradesh, during December 20-23, 1999.

Figure 1:

The rows and the columns of Q(G) are indexed by V (G), E(G) respectively. The (i, j)-entry of Q(G) is 0 if vertex i and edge \overline{j} are not incident and otherwise it is 1 or −1 according as \overline{j} originates or terminates at i respectively.

A simple verification reveals that the Laplacian matrix L(G) equals Q(G)Q(G)^{T} , where the superscript T denotes transpose. Note that although Q(G) depends on the orientation of the edges, the matrix L(G) does not depend upon the particular orientation chosen.

Example: Let G = (V (G), E(G)) be the graph shown in Figure 1, with V (G) = \{1, 2, 3, 4, 5\} and E(G) = \{\overline{1}, \overline{2}, \overline{3}, \overline{4}, \overline{5}, \overline{6}\}.

Then

A(G) = [ \begin{matrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{matrix} ] , Q(G) = [ \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 \\ −1 & 0 & 1 & 0 & 0 & −1 \\ 0 & 0 & −1 & 1 & 0 & 0 \\ 0 & −1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & −1 & −1 & 0 \end{matrix} ] ,

and

L(G) = Q(G)Q(G)^{T} = [ \begin{matrix}2 & −1 & 0 & −1 & 0 \\ −1 & 3 & −1 & −1 & 0 \\ 0 & −1 & 2 & 0 & −1 \\ −1 & −1 & 0 & 3 & −1 \\ 0 & 0 & −1 & −1 & 2 \end{matrix} ] .

Some basic properties of the Laplacian matrix are stated next. Lemma 1 Let G be a graph with n vertices. Then the following properties hold.

(i) L(G) is a symmetric, positive semidefinite matrix.

(ii) The off-diagonal entries of L(G) are nonpositive (in fact, they are either 0 or −1). The i-th diagonal entry of L(G) is d_{i}(G), i = 1, 2, …, n. The row sums and the column sums of L(G) are all zero.

(iii) The rank of L(G) is n−k, where k is the number of connected components

of G. In particular, if G is connected, then the rank of L(G) is n − 1. Property (i) of Lemma 1 follows easily since L(G) = Q(G)Q(G)^{T} . Similarly,

(ii) is immediate from the definition. For a proof of (iii) we refer to [10].

The Laplacian matrix arises in a variety of application areas such as graph isomorphism problems, electrical networks, computational techniques for differential equations, physical chemistry, biochemistry, computer science and design of statistical experiments. We refer to [1, 16 20] for further material and references concerning the Laplacian.

We now introduce some more definitions. If A is an n × m matrix, then an m × n matrix H is called a generalized inverse (or a g-inverse) of A if AHA = A. The Moore-Penrose inverse of A, is an m × n matrix H satisfying the equations

AHA = A, HAH = H, (AH)^{T} = AH and (HA)^{T} = HA.

Figure 2:

It is well-known that the Moore-Penrose inverse exists and is unique. We denote the Moore-Penrose inverse of A by A^{+}. For background material on generalized inverses, see [7, 12].

Let G = (V, E) be a connected graph. (We will often write V, E, L in place of V (G), E(G), L(G) etc.) The distance between vertices i, j ∈ V, denoted by d(i, j) is defined to be the length (i.e., the number of edges) in a shortest path from i to j in the graph. This is the classical notion of distance and is extensively studied, see [11]. However this concept of distance is not always appropriate. Consider the two graphs in Figure 2.

In both theses graphs, d(i, j) = 2. But it is evident that in the second graph there appear to be more paths connecting i and j (we might say that there is better “communication” between i and j) and hence it is reasonable that the “distance” between i and j should be smaller in the second graph in comparison to that in the first graph. This feature is not captured by the classical distance. Also the classical distance is not mathematically tractable unless the graph is a tree.

Another notion of distance has been recently proposed by some authors, see Klein and Randić [19], Chebotarev and Shamis [14]. The distance has been termed “resistance distance” in [19] in view of an interpretation of the notion via resistance in electrical networks. We will elaborate on this later in Section 7. Our main purpose in the present paper is to indicate various approaches, coming from diverse areas, that lead to an interpretation of the same notion. Some basic properties of resistance distance are also reviewd, giving new proofs in some cases.

As a starting point we formulate the following definition.

Definition Let G = (V, E) be a connected graph and let L be the Laplacian matrix of G. The resistance distance between i, j ∈ V, denoted by δ(i, j), is defined as

δ(i, j) = h_{ii} + h_{jj} − h_{ij} − h_{ji}

where H is any g-inverse of L.

We first show that the resistance distance is well-defined in that it does not depend on the g-inverse chosen. For i, j ∈ V, let e_{ij} denote the n × 1 vector with 1 at the i-th place, −1 at the j-th place and zeros elsewhere. As usual, let Q be the incidence matrix of G. If G is connected then by (iii) of Lemma 1, rank Q = rank L = n − 1. Let 1 denote the column vector of all ones of an appropriate dimension. Then 1 is in the null space of Q^{T} and L. Thus e_{ij}, being orthogonal to 1, is in the column space of Q and L. Thus there exists a vector z such that e_{ij} = Lz. Now

δ(i, j) = h_{ii} + h_{jj} − h_{ij} − h_{ji}
= e_{ij}^{T}He_{ij}
= z^{T} LHLz
= z^{T} Lz.

Thus δ(i, j) does not depend on the g-inverse of L that is chosen.

We remark that if H is a symmetric g-inverse of L, then δ(i, j) = h_{ii} + h_{jj} − 2h_{ij}. In particular, setting M = L^{+}, δ(i, j) = m_{ii} + m_{jj} − 2m_{ij}. This representation also shows that the n × n matrix with (i, j)-entry δ(i, j) is a conditionally negative definite matrix and also a distance matrix in the sense of Schoenberg, see [6] for the definitions of these terms.

2 The triangle inequality

Let G = (V, E) be a connected graph with n vertices and let ρ : V × V → R. If ρ is to represent a measure of distance between a pair of vertices then it is reasonable to expect that ρ should satisfy the following properties:

(i) (Nonnegativity) ρ(i, j) ≥ 0 for all i, j with equality if and only if i = j.

(ii) (Symmetry) ρ(i, j) = ρ(j, i).

(iii) (Triangle inequality) ρ(i, j) + ρ(j, k) ≥ ρ(i, k).

The classical distance d(i, j) clearly satisfies these properties. We now show that the properties are enjoyed by the resistance distance as well.

If n ≤ 2, then the properties are easy to prove, so assume n ≥ 3. Let L be the Laplacian matrix of G and let M = L^{+}. Since L is symmetric, so is M. Also, L is positive semidefinite and it follows that M = MLM is also positive semidefinite. Thus

δ(i, j) = e_{ij}^{T}Me_{ij} ≥ 0.

Since LML = L and MLM = M, then rank M = rank L, and as noted in Lemma 1, rank L = n−1 since G is connected. Thus any 2×2 principal minor of M is positive, i.e., for i ≠ j, m_{ii}m_{jj} > m_{ij}^{2}. It follows by the arithmetic mean - geometric mean inequality that m_{ii} + m_{jj} > 2m_{ij}. Thus for any i ≠ j,

δ(i, j) = m_{ii} + m_{jj} − 2m_{ij} > 0.

This shows that δ satisfies (i). Clearly, δ(i, j) = e_{ij}^{T}Me_{ij} = δ(j, i) and hence (ii) holds. We now show that δ satisfies (iii). For any symmetric g-inverse H of L, δ(i, j) = h_{ii} + h_{jj} − 2h_{ij}. Thus in order to prove δ(i, j) + δ(j, k) ≥ δ(i, k) we must show that

h_{ii} + h_{jj} − 2h_{ij} + h_{jj} + h_{kk} − 2h_{jk} ≥ h_{ii} + h_{kk} − 2h_{ik}

and this is equivalent to

h_{jj} + h_{ik} − h_{ij} − h_{jk} ≥ 0.  (1)

If k, ℓ ∈ V, then L(k|ℓ) will denote the submatrix of L obtained by deleting row k and column ℓ. Similarly for k_{1}, k_{2}, ℓ_{1}, ℓ_{2} ∈ V, L(k_{1}, k_{2}|ℓ_{1}, ℓ_{2}) will denote the submatrix of L obtained by deleting rows k_{1}, k_{2} and columns ℓ_{1}, ℓ_{2}. Let B = L(j|j). Then B is positive definite and the off-diagonal elements of B are nonpositive. Thus B is an M-matrix and by a well-known property of such matrices, B^{−1} is entrywise nonnegative (see, for example, Berman and Plemmons [8]). We choose the following g-inverse of L : In L, replace entries in the j-th row and column by zeros and replace L(j|j) by B^{−1}. Let the resulting matrix be H. It is easily verified that LHL = L and hence H is a g-inverse of L. Note that h_{jj} = h_{ij} = h_{jk} = 0, while h_{ik} ≥ 0 since B^{−1} ≥ 0 as remarked earlier. Thus (1) is proved and δ satisfies the triangle inequality.

The proof technique employed here has been used by Constantine and Xue [15] where the result is proved in the context of block designs in statistics. The graphs arising in such a context are necessarily bipartite (see also Section 4). In our proof the same technique is used for arbitrary graphs. A different proof of the triangle inequality based on electrical networks is found in [19].

3 Network flows

Let G = (V, E) be a connected graph and let i, j ∈ V be fixed. In this section we interpret δ(i, j) in terms of an “optimal” flow from i to j. First we give some definitions. Let the edges of G be assigned an orientation which is arbitrary but fixed and let Q be the incidence matrix of the resulting directed graph. A unit flow from i to j is defined as a function f : E → R such that

Q [ f(\overline{1}) ; f(\overline{2}) ; ⋮ ; f(\overline{m}) ] = e_{ij}.  (2)

The interpretation of (2) is easy: at each vertex other than i, j, the incoming “flow” equals the outgoing “flow”; at i the outgoing “flow” is 1 whereas at j, the incoming “flow” is 1. The norm of a unit flow f is defined to be

||f|| = \{∑_{\overline{s}∈E} f(\overline{s})^{2}\}^{\frac{1}{2}} .

Let L be the Laplacian matrix of G. As noted in Section 1, e_{ij} is in the column space of L and hence in the column space of Q. Therefore (2) is consistent. A solution of (2) with minimum norm is given by f_{0} = Q^{−}e_{ij}, where Q^{−} is a minimum norm g-inverse of Q, i.e., satisfies QQ^{−}Q = Q and that Q^{−}Q is symmetric (see [2, 21]). Since Q^{+} is a minimum norm g-inverse of Q, f_{0} = Q^{+}e_{ij} is a solution of (2) with minimum norm. Then

||f_{0}||^{2} = e_{ij}^{T}(Q^{+})^{T} Q^{+}e_{ij} = e_{ij}^{T}L^{+}e_{ij}

since L^{+} = (QQ^{T})^{+} = (Q^{T})^{+}Q^{+} = (Q^{+})^{T} Q^{+} by well-known properties of the Moore-Penrose inverse (see [12]).Thus we have proved that δ(i, j) = e_{ij}^{T}L^{+}e_{ij} is the minimum value of ||f||^{2} where ||f|| is a unit flow from i to j. This interpretation of δ(i, j) appears to be new. We now use the interpretation to calculate δ(i, j) in the following simple example:

Figure 3:

Consider the graph shown in Figure 3.

A unit flow from i to j is given by f({i, k}) = α_{k}, f({k, j}) = −α_{k}, k = 1, 2, …, p, where α_{1} + ⋯ + α_{p} = 1. Clearly

||f||^{2} = 2(α_{1}^{2} + ⋯ + α_{p}^{2})

is minimized when α_{k} = \frac{1}{p}, k = 1, 2, …, p; in which case the value of ||f||^{2} is \frac{2}{p}. It follows that δ(i, j) = \frac{2}{p}.

In the next result we show that the resistance distance is dominated by the classical distance. For different proofs of this fact see [14, 19].

Theorem 2 Let G = (V, E) be a connected graph and let i, j ∈ V. Then

δ(i, j) ≤ d(i, j).  (3)

Proof: Choose and fix an (i, j)-path P of length d(i, j). Orient each edge in P in the direction from i to j and assign an arbitrary orientation to the remaining edges of G. If g : E → R is defined as

g(\overline{k}) = \{ \begin{matrix}1 if \overline{k} ∈ P \\ 0 otherwise \end{matrix}

then g is a unit flow from i to j. Since δ(i, j) is the minimum value of the squared norm of a unit flow from i to j, we have

d(i, j) = ||g||^{2} ≥ δ(i, j)

and the proof is complete.

It can be shown that equality holds in (3) if and only if there is a unique (i, j)-path. A proof can be given along similar lines as in [3]. In particular, if G is a tree, then δ(i, j) = d(i, j) for all i, j.

4 Least squares estimation

Let G = (V, E) be a connected directed graph with n vertices. We associate a linear statistical model with the graph as follows: Corresponding to vertex k there is a parameter β_{k}, k = 1, 2, …, n. We take an observation corresponding to each edge. The observation associated with the edge \overline{k} is denoted Y_{k}. If the edge \overline{k} is directed from i to j, then we assume that E(Y_{k}) = β_{i} − β_{j} is the expected value of Y_{k}. We assume that Y_{1}, …, Y_{m} are uncorrelated with a common (unknown) variance σ^{2}. Fix i, j ∈ V and consider the problem of estimating β_{i} − β_{j} by the least squares method. Let Y = (Y_{1}, …, Y_{m})^{T} . A function ℓ^{T} Y = ℓ_{1}Y_{1} + ⋯ + ℓ_{m}Y_{m} is unbiased for β_{i} − β_{j} if E(ℓ^{T} Y) = β_{i} − β_{j} and this is equivalent to

ℓ^{T} Q = e_{ij}^{T},  (4)

where ℓ = (ℓ_{1}, …, ℓ_{m}) and e_{ij} is as defined in Section 1. A best linear unbiased estimate (BLUE) of β_{i} − β_{j} is given by ℓ_{1}Y_{1} + ⋯ + ℓ_{m}Y_{m} if ℓ = Q^{−}e_{ij}, where Q^{−} is a least squares g-inverse of Q, i.e., QQ^{−}Q = Q and QQ^{−} is symmetric. Since Q^{+} is a least squares g-inverse of Q, (Q^{+}e_{ij})^{T} Y is a BLUE of β_{i} − β_{j}. The variance of the BLUE is given by

σ^{2}(Q^{+}e_{ij})^{T} Q^{T} e_{ij} = σ^{2}e_{ij}^{T}(Q^{+})^{T} Q^{T} e_{ij}

= σ^{2}e_{ij}^{T}(QQ^{T})^{+}e_{ij}
= σ^{2}e_{ij}^{T}L^{+}e_{ij}
= σ^{2}δ(i, j).

Thus we have yet another interpretation of δ(i, j) : it is \frac{1}{σ^{2}} times the variance of the BLUE of β_{i} − β_{j} in the model described above. For a discussion of this model and some related results see [3].

The linear model based on a graph introduced above arises naturally in the context of block designs. Suppose v treatments, labelled 1, 2, …, v, are to be compared. Let the treatments be allocated to experimental units, or plots, arranged in b blocks of size k each. Let the treatment effects be τ_{1}, …, τ_{v} and the block effects be α_{1}, …, α_{b}. If a plot receives treatment i and is in block j, then the corresponding observation is assumed to have expected value τ_{i} + α_{j}. This is the linear model that is analyzed to compare the treatment effects. Set β_{j} = −α_{j}, j = 1, 2, …, b. Consider the bipartite graph with the set of treatments and the blocks as vertices and an edge directed from treatment i to block j if and only if the treatment appears in block j. Then the linear model associated with this graph, as described earlier in this section, is precisely the model of interest for comparing the treatment effects.

5 Spanning trees and spanning forests

Let G = (V, E) be a connected graph. A spanning subgraph of G is a graph G = (V, E_{1}) where E_{1} ⊂ E. Recall that a graph with no cycles is called a forest. A conected forest is a tree. A spanning tree of G is a spanning subgraph of G which is a tree. Similarly a spanning forest of G is a spanning subgraph of G which is a forest. The number of spanning trees of G is called the complexity of G and we denote it by χ(G). The following result is well-known.

Theorem 3 (The Matrix-Tree Theorem) Let G be a connected graph with Laplacian matrix L. Then all cofactors of L are equal and the common value equals χ(G), the number of spanning trees in G.

Several generalizations of Theorem 3 giving interpretations of other minors of the Laplacian are in the literature, see [4, 5, 13, 20] and the references contained therein. We indicate one such result which will be used. A k-forest is a forest with k components. Let W ⊂ V with |W | = k. We say that a spanning k-forest of G separates vertices in W if each component of the forest contains at most one (and thus precisely one) vertex of W. Theorem 4 Let G = (V, E) be a connected graph with Laplacian matrix L and let i, j ∈ V, i ≠ j. Then det L(i, j|i, j) equals the number of spanning 2-forests of G separating vertices i and j.

We now obtain an interpretation of the resistance distance in terms of spanning trees and spanning 2-forests. Let G = (V, E) be a connected graph and let i, j ∈ V. If H is a symmetric g-inverse of L, then δ(i, j) = h_{ii}+h_{jj} −2h_{ij}. As in Section 2 we choose the following g-inverse of L : In L, replace entries in the j-th row and column by zeros and replace L(j|j) by B^{−1}. Let the resulting matrix be H. Then H is a g-inverse of L. Note that h_{jj} = h_{ij} = 0, while

h_{ii} = \frac{det L(i, j|i, j)}{det L(i|i)} = \frac{det L(i, j|i, j)}{χ(G)}.

Hence

δ(i, j) = \frac{det L(i, j|i, j)}{χ(G)}.  (5)

This formula for δ(i, j) will be used in the subsequent sections.

6 A random walk on graphs

Let G = (V, E) be a connected graph. Suppose a particle moves from vertex to vertex according to the following rule: If the particle is at vertex k, then it moves to any of the neighbouring vertices with equal probability. Let i, j ∈ V, i ≠ j be fixed. For k ∈ V, let p(k) denote the probability that a particle starting at k, and moving according to the law stated above, will visit i before visiting j. Then clearly, p(i) = 1 and p(j) = 0. For k ∈ V, we denote by N (k), the set of vertices adjacent to k. A simple argument using conditional probability shows that for k ≠ i, j;

p(k) = ∑_{s∈N (k)} \frac{1}{d_{k}} p(s),  (6)

where d_{k} denotes the degree of k. We summarize equations (6), together with p(i) = 1 and p(j) = 0, in matrix notation as follows. Let L be the Laplacian matrix of G. Let e_{k} denote the k-th row of the identity matrix and let C be the matrix obtained from L by replacing its i-th and j-th rows by e_{i}^{T} and e_{j}^{T} respectively. Then (6) is equivalent to

Cp = e_{i},  (7)

where p = (p(1), …, p(k))^{T} . Since det C = det L(i, j|i, j) > 0, the system (7) has a unique solution. By Cramer’s rule the solution is given by

p(k) = (−1)^{i+k} \frac{det L(i, j|k, j)}{det L(i, j|i, j)},  (8)

for k ≠ i, j; while p(i) = 1 and p(j) = 0.

The following identity obtained by Laplace expansion will be useful.

det L(j|j) = d_{i}det L(i, j|i, j) − ∑_{k∈N (i)}(−1)^{i+k}det L(i, j|k, j).  (9)

Suppose the particle starts at i and moves according to the prescribed law. Let P (i → j) denote the probability that the particle visits j before returning to i. Then

1 − P (i → j) = ∑_{k∈N (i)} \frac{1}{d_{i}} p(k)

= \frac{1}{d_{i}} ∑_{k∈N (i)}(−1)^{i+k} \frac{det L(i, j|k, j)}{det L(i, j|i, j)} by (8)
= \frac{1}{d_{i}} \frac{d_{i}det L(i, j|i, j) − det L(j|j)}{det L(i, j|i, j)}, by (9)
= 1 − \frac{1}{d_{i}} \frac{det L(j|j)}{det L(i, j|i, j)}.

Thus

P (i → j) = \frac{1}{d_{i}} \frac{det L(j|j)}{det L(i, j|i, j)}

and hence

δ(i, j) = \frac{1}{d_{i}P (i → j)}.

We have thus obtained an interpretation of δ(i, j) in terms of the random walk on G.

There is a close connection between the interpretation of δ(i, j) in terms of the random walk and the one based on electrical networks which we discuss in the next section.

7 Effective resistance in electrical networks

Let G = (V, E) be a connected graph with n vertices and let i, j ∈ V. We think of G as an electrical network in which a unit resistance is placed along each edge. Current is allowed to enter the network only at vertex i and leave it only at j. Let v(k) denote the voltage at the vertex k. We set v(i) = 1 and v(j) = 0. By Ohm’s law the current flowing from x to y, where {xy} ∈ E, is given by v(x) − v(y). According to Kirchhoff’s law, at any point k ∈ V, k ≠ i, j;

∑_{y∈N (k)}(v(k) − v(y)) = 0.

If we set v = (v(1), …, v(n))^{T} , then v satisfies the equation

Cv = e_{i},  (10)

where C is precisely the matrix defined in Section 6. As in Section 6, the solution of (10) is given by

v(k) = (−1)^{i+k} \frac{det L(i, j|k, j)}{det L(j|j)},  (11)

for k ≠ j and v(j) = 0. The current flowing into the network at vertex i is given by the sum of the currents from y to i for each y ∈ N (i) and this equals

∑_{y∈N (i)}(v(y) − v(i)) = ∑_{y∈N (i)}(v(y) − 1) = ∑_{y∈N (i)} v(y) − d_{i}.

Carrying out this calculation using (10),(11) as in Section 6, we find that the current flowing into the network is

\frac{det L(j|j)}{det L(i, j|i, j)},

which is precisely the reciprocal of δ(i, j). The reciprocal of the current is called the “effective resistance” between i, j and this justifies the terminology “resistance distance”.

For a unified treatment of resistance distance in the context of random walks and electrical networks, see [ 9, 17, 22, 23 ].

8 Conclusion

We defined the resistance distance δ(i, j) between vertices i, j as h_{ii} + h_{jj} − h_{ij} − h_{ji} where H is any g-inverse of the Laplacian matrix of the graph. We then gave various interpretations of the resistance distance based on notions of flows, least squares estimation, determinants, spanning forests, a random walk and electrical networks. We also proved the triangle inequality for δ(i, j) and showed that δ(i, j) is dominated by the classical distance d(i, j). We have not touched upon some aspects of the resistance distance, most notably its relevance in biochemistry, see [18, 19].

Hopefully, this paper has given sufficient motivation for considering resistance distance as a notion of much depth and significance.

REFERENCES

1. R.B. Bapat, The Laplacian matrix of a graph, The Mathematics Student, 65 (1996), 214-223.

2. R.B. Bapat, Linear Algebra and Linear Models, Second Edition, Hindustan Book Agency, New Delhi, 1999.

3. R.B. Bapat, Linear estimation in models based on a graph, Linear Algebra and its Applications, 302/303 (1999), 223-230.

4. R. B. Bapat and G. Constantine, An enumerating function for spanning forests with color restrictions, Linear Algebra and Its Applications, 173 (1992), 231-237.

5. R.B. Bapat, J.W. Grossman and D.M. Kulkarni, Generalized matrix tree theorem for mixed graphs, Linear and Multilinear Algebra, 46 (1999), 299-312.

6. R.B. Bapat and T.E.S. Raghavan, Nonnegative Matrices and Applications, Encyclopedia of Mathematics and its Applications, 64, Cambridge Univ. Press, 1997.

7. A. Ben-Israel and T.N.E. Greville, Generalized Inverses: Theory and Applications, Wiley-Interscience, 1974.

8. A. Berman and R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, SIAM, Philadelphia, 1994.

9. Belá Bollobás, Modern Graph Theory, Springer-Verlag, New York, 1998.

10. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, 1976.

11. F. Buckley and F. Harary, Distances in Graphs, Addison-Wesley, Reading, Mass., 1989.

12. S. L. Campbell and C. D. Meyer, Jr., Generalized Inverses of Linear Transformations, Pitman, 1979.

13. S. Chaiken, A combinatorial proof of the all minors Matrix Tree Theorem, SIAM Journal Algebraic Discrete Methods, 3 (1982), 319-329.

14. P. Chebotarev and E. Shamis, The matrix-forest theorem and measuring relations in small social groups, Avtomatika i Telemekhanika, 9 (1997), 124-136.

15. Gregory Constantine and Lianyong Xue, Planning for specified cost and precision, Journal of Combinatorics, Information & System Sciences, 23 (1998), 433-440.

16. D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, New York, 1979.

17. P.G. Doyle and J.L. Snell, Random Walks and Electrical Networks, Math. Assoc. Am., Washington, 1984.

18. D. J. Klein, Graph geometry, graph metrics and Weiner, Communications in Mathematical Match and in Computer Chemistry, 35 (1997), 7-27.

19. D.J. Klein and M. Randić, Resistance distance, Journal of Mathematical Chemistry, 12 (1993), 81-95.

20. R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197,198 (1994), 143-176.

21. C. R. Rao, Linear Statistical Inference and Its Applications, Wiley, New York, 1973.

22. Rahul Roy, Ohm’s law, Kirchoff’s law and the drunkard’s walk, I, Resonance, 2-11 (1997), 36-47.

23. Rahul Roy, Ohm’s law, Kirchoff’s law and the drunkard’s walk, II, Resonance, 2-12 (1997), 33-38.