Resistance matrix of a weighted graph

R. B. Bapat Indian Statistical Institute New Delhi, 110016, India fax: 91-11-26856779, e-mail: rbb@isid.ac.in

Abstract

In contrast to the classical notion of distance as the length of a shortest path between two vertices, the concept of resistance distance, introduced by Klein and Randić, arises naturally from several different considerations and is more amenable to mathematical treatment. For a connected graph with n vertices, the resistance matrix of the graph is defined to be the n × n matrix with its (i, j)-entry equal to the resistance distance between the i-th and the j-th vertices. We obtain a formula for the inverse and the determinant of the resistance matrix of a weighted graph, thereby generalizing some earlier work, including that of Graham, Pollack, Lovász, Xiao and Gutman.

Key words and phrases: Resistance distance, weighted graph, Laplacian, distance matrix

1 Introduction and Notation

The distance between two vertices in a graph is traditionally defined as the length of a shortest path between the two vertices. In contrast to this notion, the concept of resistance distance, introduced by Klein and Randić [16] arises naturally from several different considerations and is more amenable to mathematical treatment. The concept has also been of interest in the chemical literature, and in particular, an analog of the classical Wiener index based on the resistance distance has been proposed. We refer to [2, 4, 8, 11, 14, 18, 19] for more information on the resistance distance and for additional references.

For a connected graph G with n vertices, let R be the resistance matrix of the graph, which is defined to be the n × n matrix with its (i, j)-entry equal to the resistance distance (to be defined later) between the i-th and the j-th vertices. It is well-known that when the graph is a tree, the resistance distance reduces to the usual distance, namely the length of the (unique) path between the two vertices. Thus R reduces to D, the distance matrix of a tree, an object that has been studied in the literature. An early, remarkable result for the distance matrix D of a tree on n vertices, due to Graham and Pollack [12], asserts that the determinant of D equals (−1)^{n−1}(n − 1)2^{n−2}, and is thus a function of only the number of vertices. In subsequent work, Graham and Lovász [13] obtained a formula for D^{−1}, among other results. Recently, the formula was extended to a weighted tree [5].

In this paper we obtain a formula for the inverse of the resistance matrix of a weighted graph, thereby generalizing the work in [13, 5]. A formula for the determinant of the resistance matrix is then derived, and is shown to reduce to the formula obtained by Xiao and Gutman [19] in the unweighted case.

We now introduce some notation. Let G = (V, E) be a graph with n vertices, labelled {1, 2, …, n}. We will assume that G is a weighted graph, thus each edge of G is assigned a weight, which is a positive real number. When the weights are all equal to 1, a weighted graph turns into an ordinary (unweighted) graph.

The weight assigned to the edge (i, j) will be denoted by w(i, j). The Laplacian matrix L of G is an n × n matrix defined as follows. For i ≠ j, the (i, j)- entry of L is zero, if vertices i and j are not adjacent, while it is −\frac{1}{w(i,j)} if i and j are adjacent. For i = 1, 2, …, n, the (i, i)-entry of L is defined to make the i-th row sum equal to zero. We will assume throughout that G is connected. Then L is singular and has rank n − 1. For basic properties of the Laplacian, see [1, 9, 17].

If H is any generalized inverse of L, (i.e., LHL = L), then the resistance distance between i and j, denoted r_{ij}, is given by r_{ij} = h_{ii} +h_{jj} −h_{ij} −h_{ji}. The definition turns out to be insensitive to the choice of the generalized inverse [2]. In particular, if L^{+} = ((ℓ_{ij}^{+})) is the Moore-Penrose inverse of L, then

r_{ij} = ℓ_{ii}^{+} + ℓ_{jj}^{+} − 2ℓ_{ij}^{+}.  (1)

We refer to [3, 7, 10] for background material on generalized inverses, and in particular, the Moore-Penrose inverse.

The matrix of resistance distances, given by R = ((r_{ij})) will be called the resistance matrix of G.

We denote the n × n matrix with each entry 1 by J, where the order should be clear from the context. Similarly the column vector of appropriate order, with each entry equal to 1 is denoted by 1. The transpose of a matrix A will be denoted by A′, as usual.

Since the null space of L is one-dimensional and is spanned by 1, the matrix L+ \frac{1}{n}J is invertible and, following the notation in [19], we set X = (L+ \frac{1}{n}J)^{−1}. Recall that L^{+} = X − \frac{1}{n}J and hence it follows from (1) that

r_{ij} = x_{ii} + x_{jj} − 2x_{ij}.  (2)

The formulation (2) indeed implies that R is a conditionally negative definite matrix. (See [6], Chapter 4, and the references contained therein.) Since R also has zero diagonal elements, it is in fact a classical distance matrix, in the sense of Schoenberg, that is, there exist n points in an euclidean space such that r_{ij} is the squared euclidean distance between the i-th and the j-th points, for each i, j. This observation puts the entire theory of distance matrices at our disposal in the study of the resistance matrix. In particular, it immediately obtains that R is nonsingular with exactly one positive eigenvalue, a fact recently observed in Xiao and Gutman [18, 19] using an alternative approach. We will not pursue the idea of viewing R as a classical distance matrix further in this paper.

Let X̃ be the diagonal matrix with x_{11}, x_{22}, …, x_{nn} along the diagonal. Then by (2),

R = X̃J + JX̃ − 2X.  (3)

If i is a vertex of G, then n(i) will denote the set of vertices adjacent to i. For i = 1, 2, …, n, let

τ_{i} = 2 − ∑_{j∈n(i)} \frac{r_{ij}}{w(i, j)}

and let τ be the column vector with components τ_{1}, …, τ_{n}.

2 Inverse of the resistance matrix

We continue to use the notation introducd in Section 1. First we prove a preliminary result.

Lemma 1 LX̃1 + \frac{2}{n}1 = τ.

Proof: Since (L + \frac{1}{n}J)X = I, we have

∑_{j∈n(i)} \frac{x_{ii}}{w(i, j)} − ∑_{j∈n(i)} \frac{x_{ij}}{w(i, j)} + \frac{1}{n} ∑_{j} x_{ij} = 1,  (4)

for i = 1, 2, …, n. Note that the row sums of L + \frac{1}{n}J are all equal to 1 and hence the row sums of X are all 1 as well. Thus it follows from (4) that

∑_{j∈n(i)} \frac{x_{ii}}{w(i, j)} − ∑_{j∈n(i)} \frac{x_{ij}}{w(i, j)} = 1 − \frac{1}{n}.  (5)

Now

τ_{i} = 2 − ∑_{j∈n(i)} \frac{r_{ij}}{w(i, j)}
= 2 − ∑_{j∈n(i)} \frac{1}{w(i, j)}(x_{ii} + x_{jj} − 2x_{ij}) by (2)
= 2 − ∑_{j∈n(i)} \frac{x_{ii}}{w(i, j)} − ∑_{j∈n(i)} \frac{x_{jj}}{w(i, j)} + 2 ∑_{j∈n(i)} \frac{x_{ij}}{w(i, j)}.  (6)

Let γ_{i} denote the i-th entry of LX̃1 + \frac{2}{n}1. Then

γ_{i} = ∑_{j∈n(i)} \frac{x_{ii}}{w(i, j)} − ∑_{j∈n(i)} \frac{x_{jj}}{w(i, j)} + \frac{2}{n}.  (7)

It follows from (5), (6) and (7) that γ_{i} = τ_{i}, i = 1, 2, …, n, and the proof is complete.

The next result is well-known for unweighted graphs (see, for example, [14], Corollary C). The proof in the weighted case is given here for completeness.

Lemma 2 ∑_{i} ∑_{j∈n(i)} \frac{r_{ij}}{w(i,j)} = 2(n − 1).

Proof: We use the well-known property, LL^{+} = I − \frac{1}{n}J in what follows. Also note that since L has zero row sums, LX = LL^{+}.

By (3), R = X̃J + JX̃ − 2X, and hence

LR = LX̃J − 2LX = LX̃J − 2LL^{+} = LX̃J − 2(I − \frac{1}{n}J).  (8)

Thus

∑_{i} ∑_{j∈n(i)} \frac{r_{ij}}{w(i, j)} = − traceLR
= − traceLX̃J + 2(n − 1)
= − traceLX̃11′ + 2(n − 1)
= −1′LX̃1 + 2(n − 1)
= 2(n − 1),

and the proof is complete.

We remark that as a consequence of Lemma 2,

1′τ = 2n − ∑_{i} ∑_{j∈n(i)} \frac{r_{ij}}{w(i, j)} = 2n − 2(n − 1) = 2.

We now prove the main result of the paper, which is evidently inspired by the formula due to Graham and Lovász [13] for the inverse of the distance matrix of a tree.

Theorem 3 R^{−1} = −\frac{1}{2}L + \frac{1}{τ′Rτ} ττ′.

Proof: As noted in (8),

LR = LX̃J − 2I + \frac{2}{n}J

and then by Lemma 1,

LR + 2I = LX̃J + \frac{2}{n}J = τ1′.  (9)

In view of the remark following Lemma 2, it follows from (9) that

(LR + 2I)τ = τ1′τ = 2τ

and hence LRτ = 0. As remarked in Section 1, R is nonsingular, while since 1′τ = 2, then τ is a nonzero vector. Thus Rτ is a nonzero vector as well. Any vector in the null space of L must be a scalar multiple of 1, and therefore it follows that Rτ = α1 for some nonzero constant α. Thus τ′Rτ = ατ′1 = 2α and hence α = \frac{τ′Rτ}{2} . Therefore

Rτ = \frac{τ′Rτ}{2} 1.  (10)

It follows from (9) and (10) that

(−\frac{1}{2}L + \frac{1}{τ′Rτ} ττ′)R = −\frac{1}{2}LR + \frac{1}{τ′Rτ} ττ′R
= I − \frac{1}{2}τ1′ + \frac{1}{τ′Rτ} (\frac{τ′Rτ}{2} )τ1′
= I,

and the proof is complete.

The formula for the inverse of the distance matrix of a tree given in [13] is indeed a consequence of Theorem 3, see Corollary 5.

3 Determinant of the resistance matrix

The weight of a spanning tree of G is the product of the edge weights of the tree. We denote by t(G) the sum of the weights of all the spanning trees of G.

Theorem 4 detR = (−1)^{n−1}2^{n−3} \frac{τ′Rτ}{t(G)} .

Proof: By Theorem 3, R^{−1} = −\frac{1}{2}L + \frac{1}{τ′Rτ} ττ′. Since by the Matrix-Tree Theorem, any cofactor of L equals t(G), it follows, using the multilinearity of the determinant, that

detR^{−1} = (−\frac{1}{2})^{n−1} \frac{t(G)}{τ′Rτ} ∑_{i} ∑_{j} τ_{i}τ_{j}
= (−\frac{1}{2})^{n−1} \frac{t(G)}{τ′Rτ} (∑_{i} τ_{i})^{2}.

Now the result follows since ∑_{i} τ_{i} = 2.

The degree of vertex i will be denoted by δ_{i}, i = 1, 2, …, n, and δ will denote the column vector with components δ_{1}, …, δ_{n}.

Corollary 5 Let G be a tree on n vertices with Laplacian L and distance matrix D. Let η be the column vector with η_{i} = 2 − δ_{i}, i = 1, 2, …, n. Then

(i) D^{−1} = −\frac{1}{2}L + \frac{1}{2(n−1)}ηη′

(ii) detD = (−1)^{n−1}(n − 1)2^{n−2}.

Proof: Theorem 3, applied to the particular situation at hand, immediately yields

D^{−1} = −\frac{1}{2}L + \frac{1}{η′Dη} ηη′.

It is easily seen, using induction on the number of vertices, that

η′Dη = ∑_{i} ∑_{j} d_{ij}(2 − δ_{i})(2 − δ_{j}) = 2(n − 1),

and therefore (i) is proved. Again, (ii) follows readily from Theorem 4 since for an unweighted tree, t(G) = 1.

As remarked earlier, (i) and (ii) of Corollary 5 are contained in [13] and [12] respectively, while a version of (i) and (ii) for a weighted tree is given in [5].

We now obtain another expression for the determinant of the resistance matrix. By Lemma 1,

τ′Rτ = (1′X̃L + \frac{2}{n}1′)R(LX̃1 + \frac{2}{n}1)
= 1′X̃LRLX̃1 + \frac{4}{n}1′X̃LR1 + \frac{4}{n^{2}} 1R1.  (11)

We set x̂ = (x_{11}, …, x_{nn})′. Since by (3), R = X̃J + JX̃ − 2X, then

LRL = −2LXL = −2LL^{+}L = −2L.  (12)

It follows from (12) that

1′X̃LRLX̃1 = −2x̂′Lx̂.  (13)

Again, using (8), LR = LX̃J − 2I + \frac{2}{n}J, and hence

1′X̃LR1 = nx̂′Lx̂.  (14)

Finally, using (3) and the fact that X has row sums 1, we have

1′R1 = 2ntrace(X) − 2n = 2ntrace(L^{+}).  (15)

It follows from (11), (13), (14), (15) that

τ′Rτ = 2x̂′Lx̂ + \frac{8}{n}trace(L^{+}).  (16)

Combining Theorem 2 and (16) we see that

det(R) = (−1)^{n−1} \frac{2^{n−1}}{nt(G)}(\frac{n}{2}x̂′Lx̂ + 2trace(L^{+})).  (17)

In the unweighted case, (17) has been proved in [19] and as remarked there, it expresses det(R) purely in terms of the eigenvalues and eignvectors of L.

Acknowledgment: The author sincerely thanks Professor Ivan Gutman for making available preprints of [18, 19].

REFERENCES

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

2. R.B. Bapat, Resistance distance in graphs, The Mathematics Student, 68 (1999), 87-98.

3. R.B. Bapat, Linear Algebra and Linear Models, Second Edition, Springer-Verlag, New York, 2000.

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

5. R.B.Bapat, S.J. Kirkland and M. Neumann, On distance matrices and Laplacians, preprint

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. Belá Bollobás, Modern Graph Theory, Springer-Verlag, New York, 1998.

9. R.A. Brualdi and H. Ryser, Combinatorial Matrix Theory, Encyclopedia of Mathematics and its Applications, 39, Cambridge Univ. Press, 1991.

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

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

12. R.L. Graham and H.O. Pollack, On the addressing problem for loop switching, Bell System Tech. J., 50 (1971), 2495-2519.

13. R.L. Graham and L. Lovász, Distance matrix polynomials of trees, Adv. in Math., 29(1) (1978), 60-88.

14. D. J. Klein, Graph geometry, graph metrics and Weiner, MATCH Commun. Math. Comput. Chem., 35 (1997), 7-27.

15. D.J. Klein, Resistance-distance sum rules, Croatica Chemica Acta, 75(2) (2002), 633-649.

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

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

18. Wenjun Xiao and Ivan Gutman, On resistance matrices, MATCH Commun. Math. Comput. Chem., 49 (2003), 67-81.

19. Wenjun Xiao and Ivan Gutman, Resistance distance and Laplacian spectrum, Theor. Chem. Acc., in press