# Some Bounds for the Kirchhoff Index of Graphs

Authors: Yujun Yang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

The resistance distance between two vertices of a connected graphG is defined as the effective resistance between them in the corresponding electrical network constructed from G by replacing each edge of G with a unit resistor. The Kirchhoff index of G is the sum of resistance distances between all pairs of vertices. In this paper, general bounds for the Kirchhoff index are given via the independence number and the clique number, respectively. Moreover, lower and upper bounds for the Kirchhoff index of planar graphs and fullerene graphs are investigated.


---

## Body

## 1. Introduction

LetG be a connected graph with vertices labeled as 1,2,…,n. It is natural to view G as an electrical network by imagining each edge of G to be a (unit) resistor. In this guise, it is reasonable to consider the effective resistance between any two vertices of G, and the novel concept ofresistance distance [1] rij(G) between any two vertices i and j of G is thus defined as the effective resistance between them. Compared to the (shortest-path) distance dij(G) between i and j in G, it is well known that rij(G)≤dij(G) with equality if and only if i and j are connected by unique path [1].There are many distance-based molecular structure descriptors, as reviewed in [2], which have played important roles in QSAR and QSPR. Among these structure descriptors, the most famous one is the Wiener index W(G) [3], which is known as the sum of distances between all pairs of vertices. Analogous to the Wiener index, the Kirchhoff index of G [1, 4], denoted by Kf(G), is defined as the sum of resistance distances between all pairs of vertices; that is,
(1)Kf(G)=∑i<j‍rij(G).As summarized in [2], much work has been done by many researchers to investigate bounds for the Kirchhoff index. There are not only general bounds that are given in terms of various graph structural parameters like the number of vertices, the number of edges, the matching number, the chromatic number, the maximum degree, and the number of spanning trees [5–20], but also bounds for some special interesting classes of graphs, such as circulant graphs, unicyclic graphs, and bicyclic graphs [21–27]. Along this line, we consider the relation between the Kirchhoff index and the independence number as well as the clique number, and bounds are obtained for the Kirchhoff index of graphs via the two graph invariants. In addition, lower and upper bounds for the Kirchhoff index of planar graphs and fullerene graphs are investigated. For more information on the Kirchhoff index of graphs, the readers are referred to the most recent papers [28–36] and references therein.


## 2. General Bounds

### 2.1. A Lower Bound via the Independence Number

We first introduce some notations. Denote the vertex set and edge set ofG, respectively, by V(G) and E(G). A subset X of V(G) is called independent if its vertices are mutually nonadjacent. The independence number α(G) is the largest cardinality among all independent sets of G. The clique number ω(G) of G is the largest set of mutually adjacent vertices in G. The degree of vertex i, denoted by di(G), is the number of neighbors of i. The adjacency matrix A(G) of G is an n×n matrix with the (i,j)-entry equal to 1 if vertices i and j are adjacent and 0 otherwise. Let D(G)=diag⁡(d1(G),d2(G),…,dn(G)) be the diagonal matrix of vertex degrees. Then the Laplacian matrix of G is L(G)=D(G)-A(G). Let λ0≤λ1≤⋯≤λn-1 be the eigenvalues of L(G), called the Laplacian eigenvalues of G. Since G is connected, λ0=0 and λk>0 for k=1,2,…,n-1 [37]. The spectrum of L(G), also known as the Laplacian spectrum of G, is
(2)S(G)=(λ0,λ1,…,λn-1).Zhu et al. [38] and Gutman and Mohar [39] established a classical result for computing the Kirchhoff index via the Laplacian spectrum of G.Theorem 1.
(3)
K
f
(
G
)
=
n
∑
k
=
1
n
-
1
‍
1
λ
k
.The join ofG1 and G2, denoted by G1+G2, is the graph obtained from G1∪G2 by adding all edges between vertices of G1 and that of G2, where ∪ denote the disjoint union. The Laplacian eigenvalues of G1+G2 are characterized in the following result.Lemma 2 (see [37]).
LetG1 and G2 be graphs such that |V(G1)|=n and |V(G2)|=m. Suppose that 0=λ0≤λ1≤λ2≤⋯≤λn-1 and 0=μ0≤μ1≤μ2≤⋯≤μm-1 are Laplacian eigenvalues of G1 and G2. Then the Laplacian eigenvalues of G1+G2 are 0, m+n, m+λi, n+μj, i=1,2,…,n-1, j=1,2,…,m-1.The nonincreasing property of the Kirchhoff index, as stated blow, plays an important role in estimating bounds for the Kirchhoff index.Lemma 3 (see [12]).
LetG be a noncomplete graph. If G′ is obtained from G by adding an edge, then Kf(G′)<Kf(G).For simplicity, if there is no confusion, we always abbreviaterij(G), dij(G), dv(G), α(G), and ω(G) to rij, dij, dv, α, and ω, respectively. Throughout the paper, we use Kn, Pn to denote the complete and path graph of order n, respectively. We use G¯ to denote the complement of G. Then the main result of this subsection is given as follows.Theorem 4.
LetG be a connected graph with n vertices and independence number α. Then
(4)Kf(G)≥n-α+n(α-1)n-α,
with equality if and only if G≅Kα¯+Kn-α.Proof.
LetG0 be a graph having the minimum Kirchhoff index among all connected graphs with n vertices and independence number α. Then by the nonincreasing property of the Kirchhoff index as given in Lemma 3, it is easily seen that G0≅Kα¯+Kn-α. Now we compute the Kirchhoff index of G0. Since it is well known that S(Kα¯)=(0,0,…,0) and S(Kn-α)=(n-α,n-α,…,n-α), by Lemma 2, we get
(5)S(G0)=(0,n-α,…,n-α︸α-1,n,…,n︸n-α).
Then according to Theorem 1, it follows that
(6)Kf(G0)=n(α-1n-α+n-αn)=n-α+n(α-1)n-α.


### 2.2. An Upper Bound via the Clique Number

LetGω be the set of graphs with n vertices and clique number ω. Let Gp denote the graph obtained by identifying one end vertex of path Pn-ω+1 with any vertex of Kω. In the following, we have shown that, among all the graphs in Gω, Gp has the maximum Kirchhoff index. To this end, we need the following two lemmas.Lemma 5 (see [40]).
LetG be a graph with a cut edge e=xy and G1 and G2 the components of G-e containing x and y, respectively. Then
(7)Kf(G)=Kf(G1)+Kf(G2)+|V(G2)|Kfx(G1)+|V(G1)|Kfy(G2)+|V(G1)||V(G2)|,
where Kfx(G) denote the sum of resistance distances between x and all the other vertices of G.Lemma 6 (see [41]).
LetT be an n vertex tree different from Pn and Sn. Then
(8)W(Sn)<W(T)<W(Pn).Theorem 7.
LetG∈Gω be different from Gp. Then
(9)Kf(G)<Kf(Gp).Proof.
Ifω=2, then Gp is a path. Noticing that the Kirchhoff index is equal to the Wiener index for trees, by Lemmas 3 and 6, the assertion holds. In the following, we assume that ω≥3.
LetG0 be the graph with the maximum Kirchhoff index and let H be the subgraph of G0 such that H≅Kω.
Claim
1 (every component of
G
0
-
H
is connected to
H
by only one edge). Suppose to the contrary that there exists a component of G0-H such that it is connected to H with edges e1,e2,…,ek(k>1). Let G1 be the graph obtained from G0 by the deletion of e2,e3,…,ek. Then it is easily seen that G1∈Gω and G1 is a proper spanning subgraph of G0. Thus by Lemma 3, we have Kf(G1)>Kf(G0), contradicting the property that G0 has the maximum Kirchhoff index.
Claim
2 (every component of
G
0
-
H
is a tree). Suppose to the contrary that there exists a component C of G0-H such that C is not a tree. Let T be a spanning tree of C. Remove from G0 all the edges in C but not in T to obtain G1. Then G1∈Gω and G1 is a proper subgraph of G0. Again by Lemma 3, we have Kf(G1)>Kf(G0), a contradiction.
Claim
3 (every component of
G
0
-
H
is a path, which connects to
H
via an end vertex). Let C be any component of G0-H. By Claims  1 and  2, we know that C is a tree and C is connected to H by a single edge e=xy (y∈C). Clearly G-e has two components, one is C, and denote the other one by G1. Then by Lemma 5,
(10)Kf(G0)=Kf(G1)+Kf(C)+|V(C)|Kfx(G1)+|V(G1)|Kfy(C)+|V(G1)||V(C)|.
Since Kf(G0) has the maximum Kirchhoff index and by Lemma 6 and the fact that the Kirchhoff index is equal to the Wiener index for trees, we know that Kf(G0) is maximized if and only if C is a path and y is an end vertex of C; the claim holds.
Claim
4 (every vertex of
H
has degree at most
ω
in
G
0
). Suppose to the contrary that there exists x∈H such that the degree of x in G0 is larger than ω. Then by Claim  1, x is connected to at least two components of G0-H. Let C1 and C2 be two such components connecting to x by edges xy1 and xy2, respectively. By Claim  3, both C1 and C2 are paths with y1 and y2 being end vertices of them. Without loss of generality, suppose that the length of C1 is less than or equal to the length of C2. Let z1 (resp., z2) be the end vertex of C1 (resp., C2) different from y1 (resp., y2), and let u be the unique neighbor of z1. Now construct a new graph G1 from G0 by first deleting the edge z1u and then adding a new edge z1z2. Clearly G1∈Gω. We show Kf(G0)<Kf(G1) so that Claim  4 is proved by contradiction. It is easily seen that, for any two vertices u, v distinct from z1,
(11)ruv(G0)=ruv(G1).
Thus to show Kf(G0)<Kf(G1), we need only to show that Kfz1(G0)<Kfz1(G1). On one hand, it is easily verified that
(12)∑a∈(V(C1)∪V(C2)∪{x})rz1a(G0)=∑a∈(V(C1)∪V(C2)∪{x})‍rz1a(G1).
On the other hand, for any vertex b that is not contained in (V(C1)∪V(C2)∪{x}), we have
(13)rz1b(G0)=rz1x(G0)+rxb(G0)<rz1x(G1)+rxb(G0)=rz1x(G1)+rxb(G1)=rz1b(G1).
Hence it follows that Kfz1(G0)<Kfz1(G1), as required.
Claim
5 (
G
-
H
has only one component). Suppose to the contrary that G-H has at least two components C1 and C2. Then by Claim  4, C1 and C2 must be connected with H via different vertices of H, say x and y. Let e1=xu and e2=yv be the two edges connecting H with C1 and C2, respectively. Then both C1 and C2 are paths with u and v being their end vertices. Suppose that the lengths of C1 and C2 are l1 and l2, respectively. Without loss of generality, we may assume that l1≤l2. Let z1 (resp., z2) be the other end vertex of C1 (resp., C2) different from u (resp., v), and let z be the unique neighbor of z1. Construct a new graph G1 from G0 by first deleting the edge zz1 and then adding a new edge between z1 and z2. Now we show Kf(G0)<Kf(G1), which thus gives the desired contradiction. For any two vertices p,q distinct from z1, it is easily seen that
(14)rpq(G0)=rpq(G1).
Thus it suffices to show that Kfz1(G0)<Kfz1(G1). On one hand,
(15)∑a∈V(C1)∪V(C2)∪{x,y}‍rz1a(G0)=1+2+⋯+l1+(l1+2ω)+(l1+1+2ω)+(l1+2+2ω)+⋯+(l1+12+2ω),
while
(16)∑a∈V(C1)∪V(C2)∪{x,y}‍rz1a(G1)=1+2+⋯+l2+(l2+1)+(l2+1+2ω)+(l2+2+2ω)+⋯+(l2+11+2ω),
which implies that
(17)∑a∈V(C1)∪V(C2)∪{x,y}‍rz1a(G0)<∑a∈V(C1)∪V(C2)∪{x,y}‍rz1a(G1).
On the other hand, for any vertex b that is not contained in (V(C1)∪V(C2)∪{x,y}), we have
(18)rz1b(G0)=rz1x(G0)+rxb(G0)<rz1y(G1)+rxb(G0)=rz1x(G1)+ryb(G1)=rz1b(G1).
Hence it follows that Kfz1(G0)<Kfz1(G1) as required.
From Claims  1–5, we deduce thatG0≅Gp, as desired.By Lemma5, simple calculation leads to
(19)Kf(Gp)=(n-ω)3-(n-ω)6+ω(n-ω)(n-ω-1)2+2(ω-1)(n-ω)ω+ω-1+ω(n-ω)=(n-ω)(n2+nω-2ω2+3ω+116-2ω)+ω-1.
Consequently, the upper bound on the Kirchhoff index is given in terms of the clique number.Theorem 8.
LetG be a connected graph with n vertices and clique number ω. Then
(20)Kf(G)≤(n-ω)(n2+nω-2ω2+3ω+116-2ω)+ω-1
with equality holds if and only if G≅Gp.


## 2.1. A Lower Bound via the Independence Number

We first introduce some notations. Denote the vertex set and edge set ofG, respectively, by V(G) and E(G). A subset X of V(G) is called independent if its vertices are mutually nonadjacent. The independence number α(G) is the largest cardinality among all independent sets of G. The clique number ω(G) of G is the largest set of mutually adjacent vertices in G. The degree of vertex i, denoted by di(G), is the number of neighbors of i. The adjacency matrix A(G) of G is an n×n matrix with the (i,j)-entry equal to 1 if vertices i and j are adjacent and 0 otherwise. Let D(G)=diag⁡(d1(G),d2(G),…,dn(G)) be the diagonal matrix of vertex degrees. Then the Laplacian matrix of G is L(G)=D(G)-A(G). Let λ0≤λ1≤⋯≤λn-1 be the eigenvalues of L(G), called the Laplacian eigenvalues of G. Since G is connected, λ0=0 and λk>0 for k=1,2,…,n-1 [37]. The spectrum of L(G), also known as the Laplacian spectrum of G, is
(2)S(G)=(λ0,λ1,…,λn-1).Zhu et al. [38] and Gutman and Mohar [39] established a classical result for computing the Kirchhoff index via the Laplacian spectrum of G.Theorem 1.
(3)
K
f
(
G
)
=
n
∑
k
=
1
n
-
1
‍
1
λ
k
.The join ofG1 and G2, denoted by G1+G2, is the graph obtained from G1∪G2 by adding all edges between vertices of G1 and that of G2, where ∪ denote the disjoint union. The Laplacian eigenvalues of G1+G2 are characterized in the following result.Lemma 2 (see [37]).
LetG1 and G2 be graphs such that |V(G1)|=n and |V(G2)|=m. Suppose that 0=λ0≤λ1≤λ2≤⋯≤λn-1 and 0=μ0≤μ1≤μ2≤⋯≤μm-1 are Laplacian eigenvalues of G1 and G2. Then the Laplacian eigenvalues of G1+G2 are 0, m+n, m+λi, n+μj, i=1,2,…,n-1, j=1,2,…,m-1.The nonincreasing property of the Kirchhoff index, as stated blow, plays an important role in estimating bounds for the Kirchhoff index.Lemma 3 (see [12]).
LetG be a noncomplete graph. If G′ is obtained from G by adding an edge, then Kf(G′)<Kf(G).For simplicity, if there is no confusion, we always abbreviaterij(G), dij(G), dv(G), α(G), and ω(G) to rij, dij, dv, α, and ω, respectively. Throughout the paper, we use Kn, Pn to denote the complete and path graph of order n, respectively. We use G¯ to denote the complement of G. Then the main result of this subsection is given as follows.Theorem 4.
LetG be a connected graph with n vertices and independence number α. Then
(4)Kf(G)≥n-α+n(α-1)n-α,
with equality if and only if G≅Kα¯+Kn-α.Proof.
LetG0 be a graph having the minimum Kirchhoff index among all connected graphs with n vertices and independence number α. Then by the nonincreasing property of the Kirchhoff index as given in Lemma 3, it is easily seen that G0≅Kα¯+Kn-α. Now we compute the Kirchhoff index of G0. Since it is well known that S(Kα¯)=(0,0,…,0) and S(Kn-α)=(n-α,n-α,…,n-α), by Lemma 2, we get
(5)S(G0)=(0,n-α,…,n-α︸α-1,n,…,n︸n-α).
Then according to Theorem 1, it follows that
(6)Kf(G0)=n(α-1n-α+n-αn)=n-α+n(α-1)n-α.


## 2.2. An Upper Bound via the Clique Number

LetGω be the set of graphs with n vertices and clique number ω. Let Gp denote the graph obtained by identifying one end vertex of path Pn-ω+1 with any vertex of Kω. In the following, we have shown that, among all the graphs in Gω, Gp has the maximum Kirchhoff index. To this end, we need the following two lemmas.Lemma 5 (see [40]).
LetG be a graph with a cut edge e=xy and G1 and G2 the components of G-e containing x and y, respectively. Then
(7)Kf(G)=Kf(G1)+Kf(G2)+|V(G2)|Kfx(G1)+|V(G1)|Kfy(G2)+|V(G1)||V(G2)|,
where Kfx(G) denote the sum of resistance distances between x and all the other vertices of G.Lemma 6 (see [41]).
LetT be an n vertex tree different from Pn and Sn. Then
(8)W(Sn)<W(T)<W(Pn).Theorem 7.
LetG∈Gω be different from Gp. Then
(9)Kf(G)<Kf(Gp).Proof.
Ifω=2, then Gp is a path. Noticing that the Kirchhoff index is equal to the Wiener index for trees, by Lemmas 3 and 6, the assertion holds. In the following, we assume that ω≥3.
LetG0 be the graph with the maximum Kirchhoff index and let H be the subgraph of G0 such that H≅Kω.
Claim
1 (every component of
G
0
-
H
is connected to
H
by only one edge). Suppose to the contrary that there exists a component of G0-H such that it is connected to H with edges e1,e2,…,ek(k>1). Let G1 be the graph obtained from G0 by the deletion of e2,e3,…,ek. Then it is easily seen that G1∈Gω and G1 is a proper spanning subgraph of G0. Thus by Lemma 3, we have Kf(G1)>Kf(G0), contradicting the property that G0 has the maximum Kirchhoff index.
Claim
2 (every component of
G
0
-
H
is a tree). Suppose to the contrary that there exists a component C of G0-H such that C is not a tree. Let T be a spanning tree of C. Remove from G0 all the edges in C but not in T to obtain G1. Then G1∈Gω and G1 is a proper subgraph of G0. Again by Lemma 3, we have Kf(G1)>Kf(G0), a contradiction.
Claim
3 (every component of
G
0
-
H
is a path, which connects to
H
via an end vertex). Let C be any component of G0-H. By Claims  1 and  2, we know that C is a tree and C is connected to H by a single edge e=xy (y∈C). Clearly G-e has two components, one is C, and denote the other one by G1. Then by Lemma 5,
(10)Kf(G0)=Kf(G1)+Kf(C)+|V(C)|Kfx(G1)+|V(G1)|Kfy(C)+|V(G1)||V(C)|.
Since Kf(G0) has the maximum Kirchhoff index and by Lemma 6 and the fact that the Kirchhoff index is equal to the Wiener index for trees, we know that Kf(G0) is maximized if and only if C is a path and y is an end vertex of C; the claim holds.
Claim
4 (every vertex of
H
has degree at most
ω
in
G
0
). Suppose to the contrary that there exists x∈H such that the degree of x in G0 is larger than ω. Then by Claim  1, x is connected to at least two components of G0-H. Let C1 and C2 be two such components connecting to x by edges xy1 and xy2, respectively. By Claim  3, both C1 and C2 are paths with y1 and y2 being end vertices of them. Without loss of generality, suppose that the length of C1 is less than or equal to the length of C2. Let z1 (resp., z2) be the end vertex of C1 (resp., C2) different from y1 (resp., y2), and let u be the unique neighbor of z1. Now construct a new graph G1 from G0 by first deleting the edge z1u and then adding a new edge z1z2. Clearly G1∈Gω. We show Kf(G0)<Kf(G1) so that Claim  4 is proved by contradiction. It is easily seen that, for any two vertices u, v distinct from z1,
(11)ruv(G0)=ruv(G1).
Thus to show Kf(G0)<Kf(G1), we need only to show that Kfz1(G0)<Kfz1(G1). On one hand, it is easily verified that
(12)∑a∈(V(C1)∪V(C2)∪{x})rz1a(G0)=∑a∈(V(C1)∪V(C2)∪{x})‍rz1a(G1).
On the other hand, for any vertex b that is not contained in (V(C1)∪V(C2)∪{x}), we have
(13)rz1b(G0)=rz1x(G0)+rxb(G0)<rz1x(G1)+rxb(G0)=rz1x(G1)+rxb(G1)=rz1b(G1).
Hence it follows that Kfz1(G0)<Kfz1(G1), as required.
Claim
5 (
G
-
H
has only one component). Suppose to the contrary that G-H has at least two components C1 and C2. Then by Claim  4, C1 and C2 must be connected with H via different vertices of H, say x and y. Let e1=xu and e2=yv be the two edges connecting H with C1 and C2, respectively. Then both C1 and C2 are paths with u and v being their end vertices. Suppose that the lengths of C1 and C2 are l1 and l2, respectively. Without loss of generality, we may assume that l1≤l2. Let z1 (resp., z2) be the other end vertex of C1 (resp., C2) different from u (resp., v), and let z be the unique neighbor of z1. Construct a new graph G1 from G0 by first deleting the edge zz1 and then adding a new edge between z1 and z2. Now we show Kf(G0)<Kf(G1), which thus gives the desired contradiction. For any two vertices p,q distinct from z1, it is easily seen that
(14)rpq(G0)=rpq(G1).
Thus it suffices to show that Kfz1(G0)<Kfz1(G1). On one hand,
(15)∑a∈V(C1)∪V(C2)∪{x,y}‍rz1a(G0)=1+2+⋯+l1+(l1+2ω)+(l1+1+2ω)+(l1+2+2ω)+⋯+(l1+12+2ω),
while
(16)∑a∈V(C1)∪V(C2)∪{x,y}‍rz1a(G1)=1+2+⋯+l2+(l2+1)+(l2+1+2ω)+(l2+2+2ω)+⋯+(l2+11+2ω),
which implies that
(17)∑a∈V(C1)∪V(C2)∪{x,y}‍rz1a(G0)<∑a∈V(C1)∪V(C2)∪{x,y}‍rz1a(G1).
On the other hand, for any vertex b that is not contained in (V(C1)∪V(C2)∪{x,y}), we have
(18)rz1b(G0)=rz1x(G0)+rxb(G0)<rz1y(G1)+rxb(G0)=rz1x(G1)+ryb(G1)=rz1b(G1).
Hence it follows that Kfz1(G0)<Kfz1(G1) as required.
From Claims  1–5, we deduce thatG0≅Gp, as desired.By Lemma5, simple calculation leads to
(19)Kf(Gp)=(n-ω)3-(n-ω)6+ω(n-ω)(n-ω-1)2+2(ω-1)(n-ω)ω+ω-1+ω(n-ω)=(n-ω)(n2+nω-2ω2+3ω+116-2ω)+ω-1.
Consequently, the upper bound on the Kirchhoff index is given in terms of the clique number.Theorem 8.
LetG be a connected graph with n vertices and clique number ω. Then
(20)Kf(G)≤(n-ω)(n2+nω-2ω2+3ω+116-2ω)+ω-1
with equality holds if and only if G≅Gp.


## 3. Planar Graphs

A planar graph is a graph which can be drawn in the plane without edges crossing. In this section, we investigate bounds for Kirchhoff index of planar graphs. The following lemma is used.Lemma 9 (see [17]).
λ
1
=
λ
2
=
⋯
λ
n
-
1 if and only if G≅Kn.Theorem 10.
For ann vertex planar graph G(n≥3),
(21)n(n-1)26(n-2)≤Kf(G)≤n3-n6.
The first equality holds if and only if G≅K3,K4, and the second does if and only if G is a path.Proof.
The upper bound is well known and we suffice to show the lower bound. Bearing in mind that, for a planar graphG, |E(G)|≤3n-6, together with the fact that ∑i=1nλi=∑i=1n-1λi=∑i=1ndi=2|E(G)|, by Cauchy-Schwarz inequality, we have
(22)∑i=1n-1‍1λi≥(n-1)22|E(G)|≥(n-1)22(3n-6)=(n-1)26(n-2).
The equality holds if and only if 1/λ1=1/λ2=⋯1/λn-1, that is, λ1=λ2=⋯=λn-1, which implies by Lemma 9 that G is a complete graph. Then the proof is completed by noticing that only K3 and K4 are planar complete graphs for n≥3.Though the lower bound is not sharp forn≥5, it can be shown that, up to a scale factor, the bound is asymptotically attainable. One example is the star graph Sn, which has Kirchhoff index (n-1)2. This indicates that the lower bound can be asymptotically attained up to a scale factor of at least 1/6. In fact, the scale factor could be improved to at least 3/6. For example, consider the planar graph G=K2+Pn-2. Since the Laplacian eigenvalues of Pn are [42]
(23)4sin2kπ2n,k=0,1,…,n-1,
by Lemma 2, we readily obtain that the Laplacian eigenvalues of G are
(24)0,n,n,2+4sin2kπ2(n-2),k=1,2,…,n-3.
Therefore, by Theorem 1, we have
(25)Kf(G)=2+n2∑k=1n-3‍11+2sin2(kπ/2(n-2))=2+n2∑k=1n-3‍12-cos⁡(kπ/(n-2)).
Now we consider the asymptotic behavior of Kf(G) as n→∞:
(26)lim⁡n→∞1n2Kf(Tn)=lim⁡n→∞(2+n2∑k=1n-3‍12-cos⁡(kπ/(n-2)))=lim⁡n→∞2n2+lim⁡n→∞12n∑k=1n-3‍12-cos⁡(kπ/(n-2))=lim⁡n→∞n-32n∑k=1n-3‍12-cos⁡(kπ/(n-2))1n-3=12lim⁡n→∞∑k=1n-3‍12-cos⁡(kπ/(n-2))1n-3=12∫01‍12-cos⁡xπdx=1233=36.
Hence Kf(Tn) grows as (3/6)n2 as n→∞, and the scale factor is improved to at least 3/6.


## 4. Fullerene Graphs

A fullerene graphG is a cubic 3-connected planar graph with exactly 12 pentagons and other hexagons. Fullerene graphs are well studied in both mathematical and chemical literatures. To give bounds for fullerene graphs, we need some preparations.The famous Foster first formula, given by Foster [43], states that
(27)∑i~j‍rij=n-1,
where i~j means i and j are adjacent. Foster’s second formula [44], also given by Foster, perhaps less well known, states that
(28)∑v‍rijdv=n-2,
where rij is measured across the end vertices of two adjacent edges iv and vj and the sum is taken over all adjacent edges. Palacios [14] extended Foster’s first and second formulae and obtained the so-called Foster third formula, which states that
(29)∑v,w‍∑i<j‍rijdvdw=n-3+∑j‍1dj∑k~j‍1dk,
where the sum is taken over all pairs of vertices i and j such that ivwj is a 3-walk. In particular, if G is k regular, then the above equation can be simply written as
(30)∑3-walks‍rijκij=(n-3)k2+nk,
where κij is the number of 3-walks from i to j.Now we give lower bounds for resistance distance between any two nonadjacent vertices inG in terms of the distance between them.Lemma 11.
LetG be a fullerene graph and let i,j∈V(G). Suppose that dij=d≥2. Then
(31)rij≥{23(2-21-(d/2)),ifdiseven,23(2-2(3-d)/2+2(-1-d)/2),otherwise.Proof.
Ifd=2, by the inequality rij≥1/di+1/dj [45], we know that rij≥1/3+1/3=2/3, as desired. Now suppose that d≥3. We distinguish the following two cases.
Case
1 (
d
is even). We partition vertices in V(G)∖{i,j} into the following parts. For k=1,2,…,(d/2)-1, let
(32)Ik={x∣x∈V(G)∖{i,j},dix=k},Jk={x∣x∈V(G)∖{i,j},djx=k},
and let Id/2 be the set of the remaining vertices. For k=1,2,…,d/2, contract Ik into a single vertex ik. For k=1,2,…,(d/2)-1, contract Jk into a single vertex jk. Then we obtain a path P of length d with multiple edges;
(33)P:(i=)i0,i1,…,i(d/2)-1,id/2,j(d/2)-1,…,j1,j0(=j).
According to the structure of G, it is easily seen that, for k=1,2,…,(d/2)-1, |Ik|≤3×2k-1, |Jk|≤3×2k-1. For k=1,2,…,(d/2)-1, since every vertex in Ik has at least on neighbor in Ik-1, the number of edges connecting ik and ik+1 is no more than 2|Ik|≤3×2k. Similarly, for k=1,2,…,(d/2)-2, the number of edges connecting jk and jk+1 is no more than 3×2k, and the number of edges connecting j(d/2)-1 and id/2 is no more than 3×2d-1. Hence, according to the series and parallel connection rules of resistors, we know that
(34)rij(P)=ri0,i1(P)+ri1,i2(P)+⋯+ri(d/2)-1,id/2(P)+rj(d/2)-1,id/2(P)+rj(d/2)-2,j(d/2)-1(P)+⋯+rj1,j2(P)+rj0,j1(P)≥13+13×2+⋯+13×2(d/2)-1+13×2(d/2)-1+13×2(d/2)-2+⋯+13×2+13=23(2-21-(d/2)).
Then by Rayleigh’s short-cut principle [46], which states that shorting certain vertices together can only decrease the resistance distances between two given vertices, whereas cutting certain edges can only increase the resistance distance between two given vertices, it follows that
(35)rij(G)≥rij(P)≥23(2-21-(d/2)).
Case
2 (
d
is odd). First partition vertices in V(G)∖{i,j} in the following way. For k=1,2,…,(d-1)/2-1, let
(36)Ik={x∣x∈V(G)∖{i,j},dix=k},
for k=1,2,…,(d-1)/2, let
(37)Jk={x∣x∈V(G)∖{i,j},djx=k},
and let I(d-1)/2 be the set of remaining vertices. Contract Ik to a single vertex ik and contract Jk to a single vertex jk, k=1,2,…,(d-1)/2. Using the same argument as the proof of Case 1, we could obtain that rij≥(2/3)(2-2(3-d)/2+2(-1-d)/2).The following result is useful.Lemma 12 (see [47]).
There are exactly(9n/2-30) pairs of vertices at distance 3 in G.Next we introduce a classical result in graph theory—Menger’s Theorem.Theorem 1313 (see [48], Menger’s Theorem).
LetG be an undirected graph, and let u and v be nonadjacent vertices in G. Then, the maximum number of pairwise internally disjoint (u,v) paths in G equals the minimum number of vertices from V(G)-{u,v} whose deletion separates u and v.Now we are ready for our main result.Theorem 14.
For ann vertex fullerene graph G, one has
(38)n22-7n4-2≤Kf(G)<n318-n2+329n18-923.Proof.
We first prove the lower bound. By Foster’s first formula,(39)∑i<jdij=1rij=n-1.
Since G is triangle free, it is obvious that the end vertices of any two adjacent edges in G are at distance 2. Hence by Foster’s second formula,
(40)∑i<jdij=2rij=3(n-2).
Since there are exactly 6n-60 pairs of vertices at distance 3 and by Lemma 11 we know that rij≥5/6 for dij=3, hence
(41)∑i<jdij=3rij≥56(9n2-30)=15n4-25.
Since for dij≥4, by Lemma 11, rij≥1, we have
(42)∑i<jdij≥4rij≥[(n2)-3n2-3n-(9n2-30)]×1=n2-19n2+30.
Hence
(43)Kf(G)=∑i<j‍rij=∑i<jdij=1rij+∑i<jdij=2rij+∑i<jdij=3rij+∑i<jdij≥4rij≥n-1+3n-2+15n4-25+n2-19n2+30=n22-7n4-2.
For the upper bound, we consider any two nonadjacent verticesi and j. Since G is 3-connected, by Menger’s Theorem, i and j are connected by at least three pairwise internally disjoint paths. Suppose that P1, P2, and P3 are three pairwise internally disjoint paths connecting i and j. We consider the graph G* induced by P1, P2, and P3. By Rayleigh’s short-cut principle, rij(G)≤rij(G*). Suppose that the lengths of P1, P2, and P3 are l1, l2, and l3, respectively. Then by the series and parallel connection rules of resistors,
(44)rij(G*)=1(1/l1)+(1/l2)+(1/l3).
Since it is obvious that l1+l2+l3≤n+1, it follows that
(45)1l1+1l2+1l3≥3n+1+3n+1+3n+1=9n+1.
Thus rij(G)≤rij(G*)≤(n+1)/9.
By Foster’s third formula (30) and noticing that there exist 3-walks which are not 3-path in G, we conclude that
(46)∑i<jdij=3rij<∑3-walks‍rijκij=(n-3)32+3n=12n-27.
Hence
(47)Kf(G)=∑i<j‍rij=∑i<jdij=1rij+∑i<jdij=2rij+∑i<jdij=3rij+∑i<jdij≥4rij<n-1+3(n-2)+12n-27+(n2-19n2+30)×n+19=n318-n2+329n18-923.



---

*Source: 794781-2014-07-10.xml*