# Bounds for the Kirchhoff Index of Bipartite Graphs

Authors: Yujun Yang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

A(m,n)-bipartite graph is a bipartite graph such that one bipartition has m vertices and the other bipartition has n vertices. The tree dumbbell D(n,a,b) consists of the path Pn−a−b together with a independent vertices adjacent to one pendent vertex of Pn−a−b and b independent vertices adjacent to the other pendent vertex of Pn−a−b. In this paper, firstly, we show that, among (m,n)-bipartite graphs (m≤n), the complete bipartite graph Km,n has minimal Kirchhoff index and the tree dumbbell D(m+n,⌊n−(m+1)/2⌋,⌈n−(m+1)/2⌉) has maximal Kirchhoff index. Then, we show that, among all bipartite graphs of order l, the complete bipartite graph K⌊l/2⌋,l−⌊l/2⌋ has minimal Kirchhoff index and the path Pl has maximal Kirchhoff index, respectively. Finally, bonds for the Kirchhoff index of (m,n)-bipartite graphs and bipartite graphs of order l
are obtained by computing the Kirchhoff index of these extremal graphs.


---

## Body

## 1. Introduction

LetG be a connected graph with vertices labeled as v1,v2,…,vn. The distance between vertices vi and vj, denoted by dG(vi,vj), is the length of a shortest path between them. The famous Wiener index W(G) [1] is the sum of distances between all pairs of vertices, that is(1.1)W(G)=∑i<jdG(vi,vj).In 1993, Klein and Randic´ [2] introduced a new distance function named resistance distance on the basis of electrical network theory. They view G as an electrical network N such that each edge of G is assumed to be a unit resistor. Then, the resistance distance between vertices vi and vj, denoted by rG(vi,vj), is defined to be the effective resistance between nodes vi and vj in N. Analogous to the Wiener index, the Kirchhoff index Kf(G) [2, 3] is defined as(1.2)Kf(G)=∑i<jrG(vi,vj).As an analogy to the famous Wiener index, the Kirchhoff index is an important molecular structure descriptor [4], and thus it is well studied in both mathematical and chemical literatures. For more information on the Kirchhoff index, the readers are referred to recent papers [5–16] and references therein.It is of interest to determine bounds for the Kirchhoff index of some classes of graphs and characterize extremal graphs as well. Along this line, much research work has been done. For a general graphG, Lukovits et al. [17] proved that Kf(G)≥n-1 with equality if and only if G is a complete graph, and they also indicated that the maximal Kirchhoff index graph is the path Pn. Palacios [18] proved that Kf(G)≤1/6(n3-n) with equality if and only if G is a path. For a circulant graph, Zhang and Yang [19] showed that(1.3)n-1≤Kf(G)≤n3-n12,where the first equality holds if and only ifG is a complete graph and the second does if and only if G is a cycle. Furthermore, tight bounds for the Kirchhoff index are also obtained for a special class of unicyclic graphs [20], bicyclic graphs [21, 22], and Cacti [23].Bipartite graphs are perhaps the most basic of objects in graph theory, both from a theoretical and practical point of view. LetG be a bipartite graph with bipartition X and Y such that X is the set of white vertices and Y is the set of black vertices. Suppose that |X|=m and |Y|=n. Such graph is also known as (m,n)-bipartite graph. Without loss of generality, we supposed that m≤n. The tree dumbbell D(n,a,b) consists of the path Pn-a-b together with a independent vertices adjacent to one pendent vertex of Pn-a-b and b independent vertices adjacent to the other pendent vertex of Pn-a-b. For instance, D(13,3,3) is referred to Figure 1.Figure 1
D(13,3,3).In the next section, we first obtain thatKm,n has the minimal Kirchhoff index among all (m,n)-bipartite graphs according to strictly increasing property of the Kirchhoff index. Then we prove that tree dumbbell D(m+n,⌊(n-m+1)/2⌋,⌈(n-m+1)/2⌉) has maximal Kirchhoff index among all (m,n)-bipartite graphs. Therefore, tight bounds for the Kirchhoff index of (m,n)-bipartite graphs are determined. In the last section, we discuss general bipartite graphs of order l. We obtain that, among all bipartite graphs of order l, complete bipartite graph K⌊l/2⌋,l-⌊l/2⌋ and path Pl have minimal and maximal Kirchhoff index, respectively. Thus bounds for the Kirchhoff index of bipartite graphs of order l are also obtained.


## 2.(m,n)-Bipartite Graphs with Extremal Kirchhoff Index

Lemma 2.1 (see [19]).
LetG be a connected graph with  n vertices and  H a connected spanning subgraph of  G. Then,  Kf(G)≤Kf(H) with equality if and only if  G=H.By Lemma2.1, the complete bipartite graph Km,n has minimal Kirchhoff index among all (m,n)-bipartite graphs. Now, we compute the Kirchhoff index of Km,n.Lemma 2.2.
(2.1)Kf(Km,n)=(m+n-1)(m2+n2)-mnmn.Proof.
ForKm,n, Klein [24] obtained that the resistance distance between two vertices of different parts is (m+n-1)/mn, the resistance distance between two vertices of m-vertex part and n-vertex part is 2/n and 2/m, respectively. Hence,
(2.2)Kf(Km,n)=mnm+n-1mn+(m2)2n+(n2)2m=(m+n-1)(m2+n2)-mnmn.In the following, we search for(m,n)-bipartite graph with maximal Kirchhoff index. By Lemma 2.1, the graph possesses maximal Kirchhoff index must be a tree since otherwise any of its spanning tree has lager Kirchhoff index than it. It is well known that the Kirchhoff index and the Wiener index concise for trees. Hence, we only need to consider the Wiener index which has been extensively studied. Now, we introduce some well-known results on the Wiener index of trees.LetPn and Sn denote n-vertex path and n-vertex star, respectively. Then we have the following.Lemma 2.3 (see [25]).
LetT be any  n-vertex tree different from  Pn and  Sn. Then,
(2.3)W(Sn)<W(T)<W(Pn).It is also obtained in [25] that(2.4)W(Sn)=(n-1)2,(2.5)W(Pn)=(n+13)=n3-n6.Lete=(x,y) be an edge of T. Let n1(e) be the number of vertices of T lying closer to x than to y, and let n2(e) be the number of vertices of T lying closer to y than to x. That is,(2.6)n1(e)=|{v∣v∈V(T),dT(v,x)<dT(v,y)}|,n2(e)=|{v∣v∈V(T),dT(v,y)<dT(v,x)}|.Theorem 2.4 (see [1]).
LetT be a  n-vertex tree. Then,
(2.7)W(T)=∑e∈E(T)n1(e)n2(e).In the following, we letWT(e)=n1(e)n2(e).Theorem 2.5.
D(m+n,⌊(n-m+1)/2⌋,⌈(n-m+1)/2⌉) has maximal Kirchhoff index among all (m,n)-bipartite graphs.Proof.
Suppose thatT is the tree possessing maximal Wiener (Kirchhoff) index among all (m,n)-bipartite graphs.
Case 1.
n=m or n=m+1. In this case, D(m+n,⌊(n-m+1)/2⌋,⌈(n-m+1)/2⌉) is the path Pm+n. By Lemma 2.3, the result holds.Case 2.
n>m+1. Let P be a longest path in T with end vertices a and b. Suppose that a′ and b′ are neighbors of a and b in P, respectively.Claim 1.
The inner vertices ofP all have degree 2 in T except for a′ and b′.
Suppose to the contrary that there exists an inner pointu of P different from a′ and b′ has degree lager than 2 and v is a neighbor of u such that v∈P. Suppose that the size of the component of T-uv containing v is k. Suppose that e1 and e2 are edges in P incident to u. Let Ca, Cb, and Cu denote the components of T-e1-e2 containing a, b, and u, respectively. We choose from Ca and Cb the one containing less vertices, say Ca. a and a′ must have one that belongs to the part containing u, say a. Let T′=T-uv+av (see Figure 2). Now we show that W(T)<W(T′) by considering the contributions of edges. Obviously, WT(uv)=WT′(av)=k(m+n-k). Let E denote the edge set of E(T)-uv=E(T′)-av, and let P′ denote the path aPu. For e∈E-E(P′), WT(e)=WT′(e). For e∈E(P′), suppose that Ca(e) and Cb(e) are components of T-e containing a and b, respectively. Then, WT(e)=|Ca(e)||Cb(e)| and WT′(e)=(|Ca(e)|+k)(|Cb(e)|-k). Then,
(2.8)WT′(e)-WT(e)=k(|Cb(e)|-|Ca(e)|-k)>k(|Cb|+k-|Ca(e)|-k)≥k(|Cb|-|Ca|)≥0.
Hence,
(2.9)W(T′)=WT′(av)+∑e∈E-E(P′)WT′(e)+∑e∈E(P′)WT′(e)>WT(uv)+∑e∈E-E(P′)WT(e)+∑e∈E(P′)WT(e)=W(T).
This contradicts the choice of T.Claim 2.
Botha and b belong to Y.
Suppose not. Then, we can distinguish the following two cases.Subcase 1.
Botha and b belong to X. By Claim 1, the inner vertices of P all have degree 2 in T; hence, the vertices of Y all belong to P, that is, n<m, a contradiction.Subcase 2.
a and b belong to different parts. Suppose that a belongs to Y. By claim 1 and n>m+1, we have dT(b′)>dT(a′)+1. Let T′=T-b′b+ab (see Figure 3). Now, we show that W(T′)<W(T). Obviously, WT′(ab)=WT(b′b). Let E1 denote the edge set of E(T)-uv=E(T′)-av, and let P1 denote the path aPb′. For e∈E1-E(P1), WT(e)=WT′(e). Suppose that the edges of P1 are aa′=e1,e2,…,el such that ei is adjacent to ei+1 for 1≤i<k. It is easy to see that WT′(e1)=2(m+n-2)>WT(e1)=m+n-1 and WT′(ei)=WT(ei+1) for 2≤i<k. What is left is to compare WT′(ek) with WT(e2). WT′(ek)=(dT(b′)-1)(m+n-dT(b′)+1) and WT(e2)=dT(a′)(m+n-dT(a′)). Then,
(2.10)WT′(ek)-WT(e2)=(dT(b′)-1-dT(a′))(m+n-dT(a′)-dT(b′)+1)≥0
since dT(b′)-1-dT(a′)>0 and m+n-dT(a′)-dT(b′)+1≥0 with equality if and only if a′ and b′ are adjacent. Hence, ∑e∈E(P1)WT′(e)>∑e∈E(P1)WT(e). Thus,
(2.11)W(T′)=WT′(ab)+∑e∈E1-E(P1)WT′(e)+∑e∈E(P1)WT′(e)>WT(b′b)+∑e∈E1-E(P1)WT(e)+∑e∈E(P1)WT(e)=W(T).
As before, this contradicts the choice of T.Claim 3.
The length ofP is 2m.
By Claims1 and 2, the vertices of X are all contained in P, the end vertices of P are both contained in Y. Hence the length of P is 2m as claimed.Claim 4.
|dT(a′)-dT(b′)|≤1. Suppose to the contrary that |dT(a′)-dT(b′)|≥2. Without less of generality, suppose that dT(b′)-dT(a′)≥2. Let T′=T-b′b+a′b. We can prove that W(T′)>W(T) by methods similar to the proof of Claim 2.
By Claims1, 2, 3, and 4, we may conclude that T=D(m+n,⌊(n-m+1)/2⌋,⌈(n-m+1)/2⌉), which implies Theorem 2.5.T (a) and T′ (b) in the proof of Claim 1.
(a)(b)T (a) and T′ (b) in the proof of Subcase 2 of Claim 2.
(a)(b)Now, we compute the Kirchhoff (Wiener) index ofD(m+n,⌊(n-m+1)/2⌋,⌈(n-m+1)/2⌉). For convenience, in what follows, we denote D(m+n,⌊(n-m+1)/2⌋,⌈(n-m+1)/2⌉) by D*.Ifm=n, D* is the path Pm+n. Hence, by (2.5),
(2.12)Kf(D*)=Kf(Pm+n)=(m+n+13).
Otherwise, let
(2.13)E1={e∈D*∣eis incident to a leaf ofD*},E2=E(D*)-E1.
For e∈E1, obviously WD*(e)=m+n-1. Noticing that D* has n-m+1 leaves,
(2.14)∑e∈E1WD*(e)=(n-m+1)(m+n-1)=n2-(m-1)2.
We can see that the induced subgraph of E2 is the path P2m-1, from which D* can be obtained by adding ⌊(n-m+1)/2⌋ pendant edges to one of its endpoint and ⌈(n-m+1)/2⌉ pendant edges to the other endpoint. Hence, the degrees of endpoints of the path P2m-1 in D* are ⌊(n-m+1)/2⌋+1 and ⌈(n-m+1)/2⌉+1, respectively. Therefore,
(2.15)∑e∈E2WD*(e)=∑i=⌊(n-m+1)/2⌋+1m+n-(⌈(n-m+1)/2⌉+1)i(m+n-i).
Hence, the Kirchhoff index of D* is
(2.16)Kf(D*)=W(D*)=∑e∈E1WD*(e)+∑e∈E2WD*(e)=n2-(m-1)2+∑i=⌊n-m+1/2⌋+1m+n-(⌈n-m+1/2⌉+1)i(m+n-i)={16(-2m+3m2-m3-6mn+6m2n+3n2+3mn2)(n-m)≡0(mod⁡2),16(-3+m+3m2-m3-6mn+6m2n+3n2+3mn2)(n-m)≡1(mod⁡2).In sum, we have our main result.Theorem 2.6.
For(m,n)-bipartite graph  G(m≤n), we have
(2.17)(m+n-1)(m2+n2)-mnmn≤Kf(G)≤{16(-2m+3m2-m3-6mn+6m2n+3n2+3mn2)(n-m)≡0(mod⁡2),16(-3+m+3m2-m3-6mn+6m2n+3n2+3mn2)(n-m)≡1(mod⁡2).
The first equality holds if and only if G=Km,n, and the second does if and only if G=D(m+n,⌊(n-m+1)/2⌋,⌈(n-m+1)/2⌉).


## 3. Bipartite Graphs with Extremal Kirchhoff Index

In this section, we consider general bipartite graphs of orderl. By Lemmas 2.1 and 2.3, one can see that the path Pl has maximal Kirchhoff index among all bipartite graphs of order l. The minimal bipartite graph of Kirchhoff index must be min1≤m≤⌊l/2⌋{Km,l-m}. By Lemma 2.2,(3.1)Kf(Km,l-m)=(l-1)(m2+(l-m)2)-m(l-m)m(l-m)=(l-1)2m2-2ml+l2m(l-m)-1=(l-1)2m(m-l)+l2m(l-m)-1=-2l+1+l2m(l-m).
Hence,(3.2)min⁡1≤m≤⌊l/2⌋{Km,l-m}=K⌊l/2⌋,l-⌊l/2⌋.It is easy to compute that(3.3)Kf(K⌊l/2⌋,l-⌊l/2⌋)=(l-1)(l2-2l⌊l/2⌋+2⌊l/2⌋2)⌊l/2⌋(l-⌊l/2⌋).Hence, we have the following result.Theorem 3.1.
For bipartite graphG of order  l, we have
(3.4)(l-1)(l2-2l⌊l/2⌋+2⌊l/2⌋2)⌊l/2⌋(l-⌊l/2⌋)≤Kf(G)≤l3-l6.
The first equality holds if and only if G=K⌊l/2⌋,l-⌊l/2⌋, and the second does if and only if G=Pl.



---

*Source: 195242-2012-04-23.xml*