A formula for the Kirchhoff index

A Formula for the Kirchhoff Index E. Bendito, A. Carmona, A. M. Encinas and J.M. Gesto Departament de Matem`atica Aplicada III Universitat Polit`ecnica de Catalunya. Espa˜na ´ Angeles Carmona, Dept. Matem`atica Aplicada III Mod. C2, Campus Nord C/ Jordi Girona Salgado 1–3 08034 Barcelona Spain Fax: 93 401 18 25 e-mail: [email protected] Abstract We show here that the Kirchhoff index of a network is the average of the Wiener capacities of its vertices. Moreover, we obtain a closed-form formula for the effective resistance between any pair of vertices when the considered network has some symmetries which allows us to give the corresponding formulas for the Kirchhoff index. In addition, we find the expression for the Foster’s n-th Formula. 1 Introduction and preliminaries The computation of the effective resistance between any pair of vertices of a network as well as the computation of the Kirchhoff index has interest in electric circuit and probabilistic theory. In the last years, it has been proved the utility of the Kirchhoff index in Chemistry as a better alternative to other parameters used for discriminating among 1 different molecules with similar shapes and structures, see for instance [1, 2]. The effective resistance and the Kirchhoff index have been computed for some class of graphs with symmetries, see [1, 3, 4]. In particular, J. L. Palacios in [5] gave a closed-form formula for the Kirchhoff index for distance-regular graphs and a class of graphs of diameter two. His approach is based on the first and second Foster’s Formula. Later, in [6] he extended these techniques to a class of graphs with diameter three by proving the so-called third Foster’s Formula. In this paper we use a different approach based on discrete Potential Theory in order to compute the effective resistances. Specifically, we consider the so-called equilibrium measures of the network associated with the combinatorial Laplacian kernel and the corresponding Wiener capacities, see [7, 8, 9]. In particular, we prove that the Kirchhoff index is nothing else but the average of the Wiener capacities of the vertices of the network. Moreover, when the network has symmetries the equilibrium measures can be computed by hand and hence we can obtain explicit formulas for the effective resistances and the Kirchhoff index. This is the case of distance-regular graphs, the so-called weighted barbell networks and the wagon wheel network that we analyze at the end of the paper. Although we do not use the Foster’s formulas in our proofs, a full generalization of those formulas can be easily obtained from the expression of the effective resistance in terms of equilibrium measures. Of course, following the Palacios’ technique the Foster’s formulas are of potential application in the computation of Kirchhoff index for graphs or networks with diameter greater than three. In this paper Γ denotes a network; that is, a simple and finite connected graph, with vertex set V={1,2, . . . , n}and edge set E, in which each edge (i, j) has been assigned a conductance cij >0. In addition, when (i, j)/∈Ewe define cij = 0 and in particular cii = 0 for any i. We define the (weighted) degree of ias δi= n X j=1 cij and the value qi= max 1≤j≤n{cij}. The matrix P= (pij),where pij =cij δi is usually called transition probability matrix of the reversible Markov chain associated with the network. More generally, for any k≥1,the k-th power of P, (p(k) ij ),is called the k-step transition probability matrix. Its ij entry is the probability that after ksteps the Markov chain attains vertex jwhen starting from vertex i. Moreover, for k≥2 this value is given by the identity p(k) ij = n X l1,...,lk−1=1 cil1cl1l2···clk−1j δiδl1· · · δlk−1 , which implies that n P j=1 p(k) ij = 1 and also that n P i=1 δip(k) ij =δj, for any k≥1. The trace of the k-step transition probability matrix is denoted by tr(Pk). The combinatorial Laplacian of Γ is the matrix Lwhose entries are Lij =−cij for all 2 i6=jand Lii =δi. Therefore, for each vector u∈IRnand for each i= 1, . . . , n (Lu)i=δiui− n X j=1 cijuj= n X j=1 cij(ui−uj).(1) It is well-known that Lu = 0 iff u=ae, a ∈IR, where eis the vector whose entries equal one. Therefore, given f∈IRn, the linear system Lu =fhas solution iff n P i=1 fi= 0 and in this case there exists a unique solution up to a constant. In addition, the combinatorial Laplacian verifies the minimum principle, see [9]. In particular, this properties implies that if u∈IRnverifies ui≥0 and (Lu)j≥0, for any j6=i, then uj≥0 for all j= 1, . . . , n. If for each i= 1, . . . , n,eidenotes the ith unit vector, with 1 in the ith position, and 0 elsewhere, the linear system Lu =e−neihas a unique solution denoted by νisuch that νi i= 0. This solution was called by some of the authors equilibrium measure of the set V\ {i}, see [9, 10]. In these references, the authors proved that any equilibrium measure can be obtained as the solution of a linear programming problem and also as the solution of a convex quadratic programming problem. The value cap(i) = n X j=1 νi jis called the Wiener capacity of vertex i. Lemma 1.1 It is verified that νi j≥1 qi for any j6=i. In addition, cap(i)≥n−1 qi and the equality holds iff cij =qifor j6=i. Proof. Consider u∈IRngiven by ui= 0 and uj=1 qi for j6=i. Then, (Lu)j=cij qi ≤1 for any j6=iand the equality holds iff cij =qi. Applying the minimum principle we obtain that νi j≥ujfor any j6=iand hence cap(i)≥ n X j=1 uj=n−1 qi . Moreover, the equality holds iff νi j=ujfor any j6=i; that is, iff cij =qifor any j6=i. 2 An explicit formula for the Kirchhoff index One of the main problems in Network Theory is to calculate the effective resistance between any pair of vertices. If i, j ∈V, the effective resistance between iand jis defined as Rij =ui−uj,where u∈IRnis any solution of the linear system Lu =ei−ej. Note that Rij does not depend on the chosen solution. Therefore, Rij =Rji and Rii = 0. The Total resistance or Kirchhoff index of the network is defined as R(Γ) = 1 2 n X i,j=1 Rij.(2) 3 The following result express the effective resistance in terms of equilibrium measures and it was proved in [9, Corollary 4.2]. We include its proof here for the sake of completeness and because it allows us to obtain directly a closed-form formula for the Kirchhoff index of Γ. Proposition 2.1 For any i, j = 1, . . . , n it is verified that Rij =1 n(νi j+νj i)and hence R(Γ) = 1 n n X i=1 cap(i). Proof. If we consider u=1 n(νj−νi),then Lu =ei−ejand hence Rij =ui−uj=1 n(νj i+νi j). Therefore, R(Γ) = 1 2n n X i,j=1 (νj i+νi j) = 1 n n X i=1 n X j=1 νi j=1 n n X i=1 cap(i). Taking into account the lower bounds for equilibrium measures and its corresponding Wiener capacities established in Lemma 1.1, we obtain the following lower bounds for the effective resistances and the Kirchhoff index. Corollary 2.2 For any 1≤i < j ≤nit is verified that Rij ≥qi+qj nqiqj .Moreover, R(Γ) ≥(n−1) n n X i=1 1 qi and the equality holds iff there exists c > 0such that cij =cfor any i, j = 1, . . . , n,i6=j; that is, iff Γis a complete network with constant conductances. Observe that when Γ is a graph then Rij ≥2 nfor any 1 ≤i < j ≤nand R(Γ) ≥n−1 with equality iff Γ is the complete graph, a well-known property, see for instance [1]. As a by-product of the expression of the effective resistance given in Proposition 2.1, we can derived a full generalization of the so-called Foster’s Identities, see [6]. We remark that the case k= 1 is the most popular Foster’s formula and the case k= 3 is, in fact, due to J.L. Palacios. 4 Proposition 2.3 For any k≥1it is verified that 1 2 n X i,j=1 δiRijp(k) ij =n−k+ k−1 X j=1 tr(Pj). Proof. First note that n X i,j=1 δiRijp(k) ij =1 n n X i,j=1 δiνi jp(k) ij +1 n n X i,j=1 δiνj ip(k) ij =2 n n X i,j=1 δiνi jp(k) ij , since δip(k) ij =δjp(k) ji .So, it suffices to prove that 1 n n X i,j=1 δiνi jp(k) ij =n−k+ k−1 X j=1 tr(Pj). Applying that Lνi=e−neiwe get that 1 n n X i,j=1 δiνi jp(k+1) ij =1 n n X i,l=1 δip(k) il n X j=1 clj δl νi j=1 n n X i,l=1 δi δl p(k) il (δlνi l+nei l−1) =1 n n X i,l=1 δip(k) il νi l+ n X i=1 p(k) ii −1 n n X i,l=1 δi δl p(k) il =1 n n X i,l=1 δip(k) il νi l+tr(Pk)−1, since n X i,l=1 δi δl p(k) il = n X l=1 1 δl n X i=1 δip(k) il =n. The result follows keeping in mind that 1 n n X i,l=1 δipilνi l=1 n n X i=1 (δiνi i+nei i−1) = n−1. Let us point out that to compute the effective resistance between any pair of vertices and hence the Kirchhoff index it suffices to solve nequilibrium problems. However, it is clear that the number of problems that we have to solve, could be drastically reduced if we have additional information about the network structure. The most striking cases appear when Γ has some type of symmetries that allow us to obtain by hand the equilibrium measures. One of the main examples of this situation is the case of distance-regular graphs. This kind of graphs have been studied by N. Biggs [11], J.L. Palacios [5] and by the authors in [7, 8]. A connected graph Γ is called distance-regular if there are integers bi, ci,i= 0, . . . , d such that for any two vertices i, j ∈Vat distance `=d(i, j), there are exactly c`neighbours of jin Γ`−1(i) and b`neighbours of jin Γ`+1(i), where Γ`(i) is the set of vertices at distance `from i. In particular, Γ is regular of degree δ=b0. Moreover, 5 ai=δ−ci−biis the number of neighbours of jin Γ`(i) and clearly, bd=c0= 0, c1= 1 and the diameter of Γ is d. The sequence ι(Γ) = {b0, b1, . . . , bd−1;c1, . . . , cd}, is called the intersection array of Γ. In addition, the number of vertices in Γ`(i) is independent of the choice of iand will be denoted by k`. Then, k0= 1, k1=δand the following equalities hold: k`=b0···b`−1 c1· · · c` , ` = 2, . . . , d or equivalently k`+1c`+1 =k`b`, ` = 2, . . . , d −1.(3) In [7] we proved that the equilibrium measure νi jdepend only on the distance between vertices iand j. Specifically, νi j= d(i,j)−1 X l=0 1 klbl d X m=l+1 kmand hence we get the following result, that was previously obtained in [5] by using a different approach. Proposition 2.4 For any i, j = 1, . . . , n it is verified that Rij =2 n d(i,j)−1 X l=0 1 klbl d X m=l+1 km and hence R(Γ) = d−1 X l=0 1 klbl³d X m=l+1 km´2. Some particular cases of the above formula are also important. For instance, we can consider the complete graph, Kn; that is the distance regular graph of diameter d= 1, whose intersection array is ι(Kn) = {n−1; 1}. Therefore, Rij =2 nfor any i6=jand R(Kn) = n−1, equality that in this case is nothing but that the so-called first Foster’s identity. We can also consider the cycle Cnon nvertices. In this case, d=bn 2cand the intersection array is given by ι(Γ) = {2,1, . . . , 1; 1, . . . , 1, cd}, where cd= 2 for even nand cd= 1 for odd n. Then, Rij =d(i, j) n³n−d(i, j)´and hence R(Cn) = n 12 (n2−1). Another interesting family of this type of graphs is formed by the so-called strongly regular graphs; that is, distance-regular graphs of diameter d= 2. Therefore if Γ is an strongly regular graph, then its intersection array is ι(Γ) = {δ, b1; 1, c2}and hence it is characterized by three parameters. Then, Rij =2(b1+c2) n c2 if d(i, j) = 1, Rij = 2(1 + b1+c2) n c2 if d(i, j) = 2 and hence R(Γ) = δ c2 2 (b1+ (c2+b1)2). We finish this paper by calculating the Kirchhoff index for two types of networks that have some symmetries but that are not distance-regular graphs; in fact, they are not even regular. 6 The first example is the so-called weighted barbell graph on n=k+m+rvertices, where m≥2 and k, r ≥1: start with a weighted path on mvertices, labeled as xk+1, ..., xk+m and attach a complete network of order k+ 1 at vertex xk+1 and a complete network of order r+1 at vertex xk+m. Denote by {x1, . . . , xk}the set of new vertices of the complete network attached to xk+1 and by {xk+m+1, . . . , xk+m+r}the set of new vertices of the complete network attached to xk+m. Moreover, the conductances are given by cij =a, 1≤i<j≤k;ci,k+1 =c0, 1 ≤i≤k;ck+i,k+i+1 =ci, 1 ≤i≤m−1; ck+m,k+m+i=cm, 1≤i≤r, and ck+m+i,k+m+j=b, 1 ≤i < j ≤r, where c0, . . . , cm>0 and a, b ≥0. Observe that when a= 0, respectively b= 0, then the attached network at vertex xk+1, respectively at vertex xk+m, is a weighted star. On the other hand, when k=r= 1, then Γ is nothing else than a weighted path on m+ 2 vertices whose conductances are c0, . . . , cm. Because the symmetries in Γ, it suffices to calculate the equilibrium measures νi, i=k, . . . , k +m+ 1. Then, the following identities are easy to verify: νk j=n ka +c0 ,1≤j≤k−1, νk k+j=(k−1) c0 +n(1 −k)a c0(ka +c0)+ j−1 X l=0 r+m−l cl ,1≤j≤m, νk k+m+j=(k−1) c0 +n(1 −k)a c0(ka +c0)+(1 −r) cm + m X l=0 r+m−l cl ,1≤j≤r, for any i= 1, . . . , m, νk+i j=(1 −k) c0 + i−1 X l=0 k+l cl ,1≤j≤k, νk+i k+j= i−1 X l=j k+l cl ,1≤j≤i−1 νk+i k+j= j−1 X l=i r+m−l cl , i + 1 ≤j≤m, νk+i k+m+j=(1 −r) cm + m X l=i r+m−l cl ,1≤j≤r, and finally, νk+m+1 j=(r−1) cm +n(1 −r)b cm(rb +cm)+(1 −k) c0 + m X l=0 k+l cl ,1≤j≤k, νk+m+1 k+j=(r−1) cm +n(1 −r)b cm(rb +cm)+ m X l=j k+l cl ,1≤j≤m, νk+m+1 k+m+j=n rb +cm ,2≤j≤r. 7 Therefore, we obtain that cap(i) = n2(k−1) k[ka +c0]+(m+r)2 kc0 +r cm + m−1 X l=1 (m+r−l)2 cl , i = 1, . . . , k, cap(k+i) = k(1 −k) c0 +r(1 −r) cm + i−1 X l=0 (k+l)2 cl + m X l=i (r+m−l)2 cl , i = 1, . . . , m, cap(k+m+i) = n2(r−1) r[rb +cm]+k c0 +(m+k)2 rcm + m−1 X l=1 (k+l)2 cl , i = 1, . . . , r. Consequently, it results that R(Γ) = n(k−1) ka +c0 +n(r−1) rb +cm +(m+r) c0 +(m+k) cm + m−1 X l=1 (k+l)(m+r−l) cl . Moreover, the formulas for the equilibrium measures imply that Rij =2 ka +c0 ,1≤i < j ≤k, Ri,k+j=(1 −k)a c0(ka +c0)+ j−1 X l=0 1 cl ,1≤i≤k, 1≤j≤m, Ri,k+m+j=(1 −k)a c0(ka +c0)+(1 −r)b cm(rb +cm)+ m X l=0 1 cl ,1≤i≤k, 1≤j≤r, Rk+i,k+j= j−1 X l=i 1 cl ,1≤i < j ≤m, Rk+i,k+m+j=(1 −r)b cm(rb +cm)+ m X l=i 1 cl ,1≤i≤m, 1≤j≤r, Rk+m+i,k+m+j=2 rb +cm ,1≤i < j ≤r. We conclude the analysis of this example by specifying the above formulas for some particular cases that have its own interest and that have been considered in the literature. When r=k= 2`−1 and m= 2`+ 1 where `≥2 and, in addition, all conductances equal 1, then Γ is called barbell graph on n= 6`−1vertices, see for instance [12]. In this case, we obtain that R(Γ) = 2 3`³26`4−9`3+ 31`2−21`+ 3´. When m= 2 and r=k=`−1, `≥2, the corresponding weighted barbell network is sometimes called weighted dumbbell network, see [12]. Then, n= 2`and R(Γ) = 2`(`−2) (`−1)a+c0 +2`(`−2) (`−1)b+c2 +(`+ 1) c0 +`2 c1 +(`+ 1) c2 . 8 If, in addition, a=band c2=c0, then R(Γ) = 4`(`−2) (`−1)a+c0 +2(`+ 1) c0 +`2 c1 . This identity was obtained in [13, Formula 39] by using a different approach based on the eigenvalues of the combinatorial Laplacian. When k=r= 1; that is, when Γ is the weighted path on n=m+ 2 vertices with conductances c0, . . . , cm, we get the well-known identity R(Γ) = m X l=0 (l+ 1)(m+ 1 −l) cl , that for unitary weights becomes R(Γ) = n 6(n2−1). Let us now consider the so-called wagon wheel network with n≥3 vertices. It consists in attaching a vertex, say n, to a weighted cycle on n−1 vertices, {1, . . . , n −1}, with uniform conductance a > 0. Moreover, the conductances of the spoke edges are ci,n =c > 0 for any i= 1, . . . , n −1. Then, we can verify straightforwardly that νn j=1 c,1≤j≤n−1 and hence cap(n) = n−1 c. To calculate the equilibrium measures νi, 1 ≤i≤n−1, we need to remember some properties of the First and Second order Chebyshev Polynomials, that are respectively defined by the following recurrences: T0(x) = 1, T1(x) = x, Tm+2(x) = 2 x Tm+1(x)−Tm(x), m ≥0, U−2(x) = −1, U−1(x) = 0, Um(x) = 2 x Um−1(x)−Um−2(x), m ≥0. (4) Moreover, for any m≥0 we have that Tm(x) = xUm−1(x)−Um−2(x) and also that 2(x−1) m P l=0 Ul(x) = Um+1(x)−Um(x)−1, for any x∈IR. Tacking into account the above properties, it is easy to verify that if q= 1 + c 2a, then for any 1 ≤i≤n−1 the values of the equilibrium measure νiare given by νi j=n 2ahTn−1(q)−1ihUn−2(q)−U|i−j|−1(q)−Un−2−|i−j|(q)i,1≤j≤n−1, νi n=nUn−2(q) 2ahTn−1(q)−1i−1 c, which implies that cap(i) = νi n+ n−1 X l=1 νi l=nνi n−1 c, since (n−1)cνi n−c n−1 X l=1 νi l= 1. Therefore, R(Γ) = 1 nhcap(n)+(n−1)cap(1)i= (n−1)ν1 nand hence R(Γ) = n(n−1)Un−2(q) 2ahTn−1(q)−1i−(n−1) c. 9