# The Kirchhoff Index of Hypercubes and Related Complex Networks

Authors: Jiabao Liu; Jinde Cao; Xiang-Feng Pan; Ahmed Elaiw
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

The resistance distance between any two vertices ofG is defined as the network effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index Kf(G) is the sum of resistance distances between all the pairs of vertices in G. We firstly provided an exact formula for the Kirchhoff index of the hypercubes networks Qn by utilizing spectral graph theory. Moreover, we obtained the relationship of Kirchhoff index between hypercubes networks Qn and its three variant networks l(Qn), s(Qn), t(Qn) by deducing the characteristic polynomial of the Laplacian matrix related networks. Finally, the special formulae for the Kirchhoff indexes of l(Qn), s(Qn), and t(Qn) were proposed, respectively.


---

## Body

## 1. Introduction

In this work we are concerned with finite undirected connected simple graphs. For the graph theoretical definitions and notations we follow [1]. A network is usually modelled by connected graphs G=(V,E), where V denotes the set of processors and E denotes the set of communication links between processors. It is well known that the standard distance between two vertices of G, denoted by dij, is the shortest path connecting the two vertices. The Wiener index [2], denoted by W(G), is a famous distance-based topological index and is defined as the sum of distances between all the pairs of vertices in G:
(1)W(G)=∑i<j‍dij(G).As an analogue to the Wiener indexW(G), another novel distance function named resistance distance was firstly proposed by Klein and Randić [3]. The resistance distance between two arbitrary in an electrical networks, many properties over resistance distances have been actually proved [2, 4–9]. The resistance distance between any two vertices of G is defined as the networks effective resistance between them if each edge of G is replaced by a unit resistor. They also defined the Kirchhoff index Kf(G) of G as the sum of resistance distances between all pairs of vertices in G; that is,
(2)Kf(G)=∑i<j‍rij(G).Klein and Randić [3] proved that rij≤dij and Kf(G)≤W(G) with equality if and only if G is a tree; it is shown that the Kirchhoff index has very nice purely mathematical and physical interpretations.The Kirchhoff index has wide applications in physical interpretations, electric circuit, graph theory, and chemistry [10–15]. For example, Zhu et al. [16] and Gutman and Mohar [17] proved that the Kirchhoff index of a graph or networks is the sum of reciprocal nonzero Laplacian eigenvalues of the graph or networks multiplied by the number of the vertices. The Kirchhoff index also is a structure descriptor like the Wiener index [9]. The Kirchhoff index has been computed for cycles [4], geodetic graphs [5], and some fullerenes including buckminsterfullerenes [6]. The Kirchhoff index of some product graphs, join graphs, and corona graphs was studied [8]. More results of the applications on Kirchhoff index were explored in [2, 7, 10, 14].The hypercubes networkQn obtained considerable attention due to its perfect properties, such as symmetry, regular structure, strong connectivity, and small diameter [18, 19]. For more results on the hypercubes network and its applications, see [18–25]. As the importance the hypercubes networks Qn, many variants of it were presented, among which, for instance, are generalized hypercubes, folded hypercubes, the line graphs of hypercubes l(Qn), the subdivision graphs of hypercubes s(Qn), and the total graphs of hypercubes t(Qn) [19, 20].The hypercubes networksQn may be constructed from the family of subsets of a set with a binary string of length n, by making a vertex for each possible subset and joining two vertices by an edge whenever the corresponding subsets differ in a single binary string. The hypercubes networks Qn admits several definitions of which two are stated as follows [26].Definition 1 (see [26]).
The hypercubes networksQn has 2n vertices each labelled with a binary string of length n. Two vertices X=x1x2⋯xn and Y=y1y2⋯yn are adjacent if and only if there exists an i, 1≤i≤n, such that xi=yi¯, where yi¯ denoted the complement of binary digit yi and xj=yj, for all j≠i, and 1≤j≤n.Definition 2 (recursive construction [26]).
The hypercubes networkQn is recursively constructed by taking two copies of Qn-1, denoted by Qn-10 and Qn-11, and adding 2n-1 edges as follows: let V(Qn-10)={0U=0u2u3⋯un:ui=0or1} and V(Qn-11)={1V=1v2v3⋯vn:vi=0or1}. A vertex 0U=0u2u3⋯un of Qn-10 is joined to a vertex 1V=1v2v3⋯vn of Qn-11 if and only if ui=vi for every i,2≤i≤n.At the end of [10], the authors presented a problem to consider the Kirchhoff index derived from a single graph, such as the line graph, the subdivision graph and the total graph Gao et al. [27] obtained special formulae for the Kirchhoff index of l(G), s(G), and t(G), where G is a regular graph. Motivated by the previous results, we present the corresponding formulae for the Kirchhoff index of the hypercubes network Qn and its three variant networks l(Qn), s(Qn), and t(Qn) in this paper.The remainder of this paper is organized as follows. Section2 gives some basic notations and some preliminaries in our discussion. The proofs of our main results are in Section 3. Finally, some conclusions are given in Section 4.


## 2. Notations and Some Preliminaries

In this section, we recall some basic notations and results in graphs theory. The adjacency matrixA(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. Suppose that D(G)=diag(d1(G),d2(G),…,dn(G)) is the degree diagonal matrix of G, where di(G) is the degree of the vertex i, i=1,2,…,n. Let L(G)=D(G)-A(G) be called the Laplacian matrix of G. Then the eigenvalues of A(G) and L(G) are called eigenvalues and Laplacian eigenvalues of G, respectively. For more details the readers may refer to [1].Yin and Wang [28] proved the following Lemma.Lemma 3 (see [28]).
For the hypercubes networksQn with n≥2,
(3)Spec(Qn)=(02⋯2i⋯2nCn0Cn1⋯Cni⋯Cnn),
where the 2i(i=0,1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks, and Cni are the multiplicities of the eigenvalues 2i.Gutman and Mohar [17] and Zhu et al. [16] presented the Kirchhoff index of a graph in terms of Laplacian eigenvalues as follows.Lemma 4 (see [16, 17]).
LetG be a connected graph with n≥2 vertices; then
(4)Kf(G)=n∑i=1n-1‍1λi.LetP(G)(x) be the characteristic polynomial of the Laplacian matrix of a graph G, the following results were shown in [27].Lemma 5 (see [27]).
LetG be an r-regular connected graph with n vertices and m edges; then
(5)Pl(G)(x)=(x-2r)m-nPG(x),Ps(G)(x)=(-1)m(2-x)m-nPG(x(r+2-x)),Pt(G)(x)=(-1)m(r+1-x)nPt(G)(x)=×(2r+2-x)m-nPG(x(r+2-x)r-x+1),
where Pl(G)(x), Ps(G)(x), and Pt(G)(x) are the characteristic polynomials for the Laplacian matrix of graphs l(G), s(G), and t(G), respectively.It is worthwhile to note that the conclusion of Lemma 5 is not completely correct, the authors [29] recently show the Laplacian characteristic polynomial of t(G), where G is a regular graph, which correct the Lemma 5 in Gao et al. [27] (2012) as follows.Lemma 6 (see [29]).
LetG be a r-regular connected graph with n vertices and m edges, then
(6)Ps(G)(x)=(-1)n(2-x)m-nPG(x(r+2-x)),Pt(G)(x)=x(x-r-2)(x-2r-2)m-nPt(G)(x)=×∏i=1n-1‍[(x2-2x-rx)+(3-2x+r)μi+μi2].
where Ps(G)(x), Pt(G)(x) are the characteristic polynomial for the Laplacian matrix of graphs s(G) and t(G), respectively.The following Lemma give an expression onKf(t(G)) and Kf(G) of a regular graph G.Lemma 7 (see [29]).
LetG be a r-regular connected graph with n vertices and m edges, and r≥2, then
(7)Kf(t(G))=(r+2)22(r+3)Kf(G)+n2(r2-4)8(r+1)+n2+n(r+2)(r+4)2(r+3)∑i=1n-1‍1μi+3+r.For proving the formula of the Kirchhoff index on the subdivision graph of hypercubes, we prove the following Lemma by utilizing Vieta’s Theorem; in our proof, some techniques in [27] are referred to.Lemma 8.
LetPQn(x) be the characteristic polynomial of the Laplacian matrix of the hypercubes networks Qn with n≥2 and
(8)PQn(x)=x2n+a1x2n-1+a2x2n-2+⋯+a2n-1x;
then
(9)Kf(Qn)2n=-a2n-2a2n-1,
where a2n-1,a2n-2 are the coefficients of x and x2 in the characteristic polynomial, respectively.Proof.
Let Spec(Qn)=(λ0,λ1,λ2,…λn,λn+1,…,λ2n-1). Then λi,i=1,2,…,2n-1 satisfy the following equation:
(10)x2n-1+a1x2n-2+⋯+a2n-1=0;
it is not difficult to check that 1/λi,i=1,2,…,2n-1 are the roots of equation
(11)a2n-1x2n-1+a2n-2x2n-2+⋯+a1x+1=0.
Note thatQn is connected graph and the multiplicity of 0 as an eigenvalue of L(Qn) is equal to the number of the connected components in Qn. So, a2n-1≠0; by Lemma 4 and Vieta’s Theorem
(12)Kf(Qn)2n=∑i=12n-1‍1λi=-a2n-2a2n-1,
where a2n-1,a2n-2 are the coefficients of x and x2 in the characteristic polynomial of the Laplacian matrix of the hypercubes networks Qn.


## 3. Main Results

### 3.1. The Kirchhoff Index in Hypercubes NetworksQn

In this section, we firstly give formula for the Kirchhoff index in the hypercubesQn with n≥2.Theorem 9.
For the hypercubes networksQn with n≥2,
(13)Kf(Qn)=2n∑i=1n‍Cni2i,
where the 2i(i=1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.Proof.
Since the hypercubes networksQn have 2n vertices and n2n-1 edges, then by Lemma 3,
(14)Spec(Qn)=(02⋯2i⋯2nCn0Cn1⋯Cni⋯Cnn);
then
(15)Kf(Qn)=2n∑i=12n-1‍1λi=2n(Cn12×1+Cn22×2+⋯+Cni2×n-1+⋯+Cnn2×n)=2n∑i=1n‍Cni2i.
The proof of Theorem 9 is completed.Remark 10.
Palacios and Renom studied the Kirchhoff index of the d-dimensional hypercube in [5] by using probabilistic tools, where they obtained a closed-form formula for the Kirchhoff index and found the asymptotic value 22d/d. We present the formula for Kirchhoff index by directly calculating the eigenvalues of the Laplacian matrix of hypercubes networks, which is different from their technique and results.


### 3.2. The Kirchhoff Index in the Line Graph of Hypercubes Networksl(Qn)

The line graph of a graphG, denoted by l(G), is the graph whose vertices correspond to the edges of G, in which two vertices are adjacent if and only if the corresponding edges of G share a common vertex. In the following theorem, we proposed a formula for the Kirchhoff index in the line graph of hypercubes networks l(Qn), denoted by Kf(l(Qn)), where the eigenvalues of Qn are λ0≤λ1≤λ2≤⋯≤λn≤λn+1≤⋯≤λ2n-1.Theorem 11.
Letl(Qn) be line graphs of hypercubes Qn with n≥2; then
(16)Kf(l(Qn))=n2n-1∑i=1n‍Cni2i++n22n-3-22n-2,
where the 2i(i=1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.Proof.
Now, for convenience, we denoted the numbers of vertices and edges in the hypercubes networksQn by p and q, respectively. Obviously, p=2n,q=n2n-1, so the line graphs of hypercubes l(Qn) have q=n2n-1 vertices.
By Lemma5,
(17)Pl(Qn)(x)=(x-2r)q-pPG(x).
Comparing the spectrum ofQn,
(18)Spec(Qn)=(02⋯2i⋯2nCn0Cn1⋯Cni⋯Cnn).
We can easily obtain the spectrum ofl(Qn) as follows:
(19)Spec(l(Qn))=(2n2n⋯2nλ0⋯λ2n-1),
where λ0,λ1,…λn,λn+1,…,λ2n-1 are the eigenvalues of Qn and λ0≤λ1≤λ2≤⋯λn≤λn+1≤⋯≤λ2n-1.
Notice that the line graphs of hypercubesl(Qn) have q=n2n-1 vertices; by Lemma 4,
(20)Kf(l(Qn))=q(∑i=12n-1‍1λi+q-p2n)(21)=n2n-12nKf(Qn)+q2-pq2n(22)=n2Kf(Qn)+n22n-3-22n-2.
Substituting the results of Theorem9 (15) into (22), we can get the formula for the Kirchhoff index on the line graph of hypercubes Kf(l(Qn)) as follows:
(23)Kf(l(Qn))=n2n-1∑i=1n‍Cni2i+n22n-3-22n-2.
This completes the proof.


### 3.3. The Kirchhoff Index in the Subdivision Graph of Hypercubes Networkss(Qn)

The subdivision graph of a graphG, denoted by s(G), is the graph obtained by replacing every edge in G with a copy of P2 (path of length two). In an almost identical way as Theorem 11, we required the formula for the Kirchhoff index in the subdivision graph of hypercubes s(Qn), denoted by Kf(s(Qn)).Theorem 12.
Lets(Qn) be subdivision graphs of the hypercubes Qn with n≥2; then
(24)Kf(s(Qn))=(n+2)(2n+n2n-1)×∑i=1nCni2i+2n-1+n222n-3-22n-1,
where the 2i(i=1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.Proof.
Now supposing thatn≥2, P(Qn)(x) is the characteristic polynomial of the Laplacian matrix of the hypercubes Qn, PQn(x)=x2n+a1x2n-1+a2x2n-2+⋯+a2n-1x, and
(25)Spec(Qn)={λ0,λ1,λ2,…λn,λn+1,…,λ2n-1},
where λi,i=0,1,2,…,2n-1 are the Laplacian eigenvalues of Qn Then by Lemma 8,
(26)Kf(Qn)2n=-a2n-2a2n-1.
By Lemma 5, we have
(27)Ps(Qn)(x)=(-1)p(2-x)q-p×[x2n(n+2-x)2n+a1x2n-1(n+2-x)2n-1+⋯+a2n-2x2(n+2-x)2+a2n-1x(n+2-x)x2n(n+2-x)2n].
Consequently, the coefficient ofx2 in Ps(Qn)(x) is
(28)a2n-2=(-1)p2q-p[(n+2)2a2n-2-2q-pa2n-1-(q-p)2q-p-1(n+2)a2n-1],
and the coefficient of x in Ps(Qn)(x) is
(29)(-1)p2q-p(n+2)a2n-1.
Note that s(Qn) has 2n+n2n-1 vertices. By Lemma 6 and substituting the coefficients into (26),
(30)Kf(s(G))2n+n2n-1=-(2q-p(n+2)2a2n-2-2q-pa2n-1-(q-p)2q-p-1a2n-1(n+2))×(2q-pa2n-1(n+2))-1(31)=-a2n-2(n+2)a2n-1+1n+2+q-p2.
By substituting q=n2n-1,p=2n and the results of Lemma 5 into (31), we have
(32)Kf(s(Qn))2n+n2n-1=-a2n-2(n+2)a2n-1+1n+2+n2n-1-2n2(33)=(n+2)Kf(Qn)2n+1n+2+n2n-1-2n2.
Simplifying (33) and substituting the results of Theorem 9 (15), we can get the formula of the Kirchhoff index on the subdivision graph of the hypercubes Kf(s(Qn)) as follows:
(34)Kf(s(Qn))=(n+2)(2n+n2n-1)2nKf(Qn)+2n+n2n-1n+2+(2n+n2n-1)(n2n-1-2n)2=(n+2)(2n+n2n-1)2nKf(Qn)+2n-1+n222n-3-22n-1=(n+2)(2n+n2n-1)×∑i=1n‍Cni2i+2n-1+n222n-3-22n-1.
Thus, the results of the Theorem 12 hold.


### 3.4. The Kirchhoff Index in the Total Graph of Hypercubes Networkst(Qn)

The total graph of a graphG, denoted by t(G), is the graph whose vertices correspond to the union of the set of vertices and edges of G, with two vertices of t(G) being adjacent if and only if the corresponding elements are adjacent or incident in G. We now proved the formula of the Kirchhoff index in the total graph of the hypercubes networks t(Qn), denoted by Kf(t(Qn)).Theorem 13.
Lett(Qn) be the total graphs of the hypercubes networks Qn with n≥2; then
(35)Kf(t(Qn))=2n-1(n+2)2n+3∑i=1n‍Cni2i+n4-4n28(n+1)+n2+(n2+2n)(n+4)2(n+3)∑i=1n‍Cni2i+3+n,
where the 2i(i=0,1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.Proof.
Let(36)Pt(Qn)(x)=x2n+a1x2n-1+a2x2n-2+…+a2n-1x.
Then by Lemma 8,
(37)Kf(t(Qn))2n=-a2n-2a2n-1.
Applying Lemma 6, the Laplacian characteristic polynomial of t(Qn) is
(38)Pt(Qn)(x)=x(x-n-2)(x-2n-2)q-pPt(Qn)(x)=×∏i=12n-1‍{[x2-2x-nx]+[3-2x+n]λi+λi2}Pt(Qn)(x)=x(x-n-2)(x-2n-2)q-pPt(Qn)(x)=×∏i=12n-1‍[x2-(2+n+2λi)x+λi2+(n+3)λi].
Consider that Qn has 2n vertices and r=n, by Lemma 7, we can get the following equality,
(39)Kf(t(Qn))=(r+2)22(r+3)Kf(Qn)+n2(r2-4)8(r+1)+n2Kf(t(Qn))=+n(r+2)(r+4)2(r+3)∑i=12n-1‍1λi+3+rKf(t(Qn))=(n+2)22(n+3)Kf(Qn)+n4-4n28(n+1)+n2Kf(t(Qn))=+(n2+2n)(n+4)2(n+3)∑i=12n-1‍1λi+3+n.
Consequently, the relationships between the hypercubes networks Qn and its variant networks t(Qn) for Kirchhoff index is
(40)Kf(t(Qn))=(n+2)22(n+3)Kf(Qn)+n4-4n28(n+1)+n2Kf(t(Qn))=+(n2+2n)(n+4)2(n+3)∑i=12n-1‍1λi+3+n.
Substitutes the result of Theorem 9 and simplifies about equation, we can get the formula for the Kirchhoff index on the total graph of hypercubes networks Kf(t(Qn)) as follows.
(41)Kf(t(Qn))=(n+2)22(n+3)Kf(Qn)+n4-4n28(n+1)+n2Kf(t(Qn))=+(n2+2n)(n+4)2(n+3)∑i=12n-1‍1λi+3+nKf(t(Qn))=2n-1(n+2)2n+3∑i=1n‍Cni2i+n4-4n28(n+1)+n2Kf(t(Qn))=+(n2+2n)(n+4)2(n+3)∑i=1n‍Cni2i+3+n.
This completes the proof of the Theorem.


## 3.1. The Kirchhoff Index in Hypercubes NetworksQn

In this section, we firstly give formula for the Kirchhoff index in the hypercubesQn with n≥2.Theorem 9.
For the hypercubes networksQn with n≥2,
(13)Kf(Qn)=2n∑i=1n‍Cni2i,
where the 2i(i=1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.Proof.
Since the hypercubes networksQn have 2n vertices and n2n-1 edges, then by Lemma 3,
(14)Spec(Qn)=(02⋯2i⋯2nCn0Cn1⋯Cni⋯Cnn);
then
(15)Kf(Qn)=2n∑i=12n-1‍1λi=2n(Cn12×1+Cn22×2+⋯+Cni2×n-1+⋯+Cnn2×n)=2n∑i=1n‍Cni2i.
The proof of Theorem 9 is completed.Remark 10.
Palacios and Renom studied the Kirchhoff index of the d-dimensional hypercube in [5] by using probabilistic tools, where they obtained a closed-form formula for the Kirchhoff index and found the asymptotic value 22d/d. We present the formula for Kirchhoff index by directly calculating the eigenvalues of the Laplacian matrix of hypercubes networks, which is different from their technique and results.


## 3.2. The Kirchhoff Index in the Line Graph of Hypercubes Networksl(Qn)

The line graph of a graphG, denoted by l(G), is the graph whose vertices correspond to the edges of G, in which two vertices are adjacent if and only if the corresponding edges of G share a common vertex. In the following theorem, we proposed a formula for the Kirchhoff index in the line graph of hypercubes networks l(Qn), denoted by Kf(l(Qn)), where the eigenvalues of Qn are λ0≤λ1≤λ2≤⋯≤λn≤λn+1≤⋯≤λ2n-1.Theorem 11.
Letl(Qn) be line graphs of hypercubes Qn with n≥2; then
(16)Kf(l(Qn))=n2n-1∑i=1n‍Cni2i++n22n-3-22n-2,
where the 2i(i=1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.Proof.
Now, for convenience, we denoted the numbers of vertices and edges in the hypercubes networksQn by p and q, respectively. Obviously, p=2n,q=n2n-1, so the line graphs of hypercubes l(Qn) have q=n2n-1 vertices.
By Lemma5,
(17)Pl(Qn)(x)=(x-2r)q-pPG(x).
Comparing the spectrum ofQn,
(18)Spec(Qn)=(02⋯2i⋯2nCn0Cn1⋯Cni⋯Cnn).
We can easily obtain the spectrum ofl(Qn) as follows:
(19)Spec(l(Qn))=(2n2n⋯2nλ0⋯λ2n-1),
where λ0,λ1,…λn,λn+1,…,λ2n-1 are the eigenvalues of Qn and λ0≤λ1≤λ2≤⋯λn≤λn+1≤⋯≤λ2n-1.
Notice that the line graphs of hypercubesl(Qn) have q=n2n-1 vertices; by Lemma 4,
(20)Kf(l(Qn))=q(∑i=12n-1‍1λi+q-p2n)(21)=n2n-12nKf(Qn)+q2-pq2n(22)=n2Kf(Qn)+n22n-3-22n-2.
Substituting the results of Theorem9 (15) into (22), we can get the formula for the Kirchhoff index on the line graph of hypercubes Kf(l(Qn)) as follows:
(23)Kf(l(Qn))=n2n-1∑i=1n‍Cni2i+n22n-3-22n-2.
This completes the proof.


## 3.3. The Kirchhoff Index in the Subdivision Graph of Hypercubes Networkss(Qn)

The subdivision graph of a graphG, denoted by s(G), is the graph obtained by replacing every edge in G with a copy of P2 (path of length two). In an almost identical way as Theorem 11, we required the formula for the Kirchhoff index in the subdivision graph of hypercubes s(Qn), denoted by Kf(s(Qn)).Theorem 12.
Lets(Qn) be subdivision graphs of the hypercubes Qn with n≥2; then
(24)Kf(s(Qn))=(n+2)(2n+n2n-1)×∑i=1nCni2i+2n-1+n222n-3-22n-1,
where the 2i(i=1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.Proof.
Now supposing thatn≥2, P(Qn)(x) is the characteristic polynomial of the Laplacian matrix of the hypercubes Qn, PQn(x)=x2n+a1x2n-1+a2x2n-2+⋯+a2n-1x, and
(25)Spec(Qn)={λ0,λ1,λ2,…λn,λn+1,…,λ2n-1},
where λi,i=0,1,2,…,2n-1 are the Laplacian eigenvalues of Qn Then by Lemma 8,
(26)Kf(Qn)2n=-a2n-2a2n-1.
By Lemma 5, we have
(27)Ps(Qn)(x)=(-1)p(2-x)q-p×[x2n(n+2-x)2n+a1x2n-1(n+2-x)2n-1+⋯+a2n-2x2(n+2-x)2+a2n-1x(n+2-x)x2n(n+2-x)2n].
Consequently, the coefficient ofx2 in Ps(Qn)(x) is
(28)a2n-2=(-1)p2q-p[(n+2)2a2n-2-2q-pa2n-1-(q-p)2q-p-1(n+2)a2n-1],
and the coefficient of x in Ps(Qn)(x) is
(29)(-1)p2q-p(n+2)a2n-1.
Note that s(Qn) has 2n+n2n-1 vertices. By Lemma 6 and substituting the coefficients into (26),
(30)Kf(s(G))2n+n2n-1=-(2q-p(n+2)2a2n-2-2q-pa2n-1-(q-p)2q-p-1a2n-1(n+2))×(2q-pa2n-1(n+2))-1(31)=-a2n-2(n+2)a2n-1+1n+2+q-p2.
By substituting q=n2n-1,p=2n and the results of Lemma 5 into (31), we have
(32)Kf(s(Qn))2n+n2n-1=-a2n-2(n+2)a2n-1+1n+2+n2n-1-2n2(33)=(n+2)Kf(Qn)2n+1n+2+n2n-1-2n2.
Simplifying (33) and substituting the results of Theorem 9 (15), we can get the formula of the Kirchhoff index on the subdivision graph of the hypercubes Kf(s(Qn)) as follows:
(34)Kf(s(Qn))=(n+2)(2n+n2n-1)2nKf(Qn)+2n+n2n-1n+2+(2n+n2n-1)(n2n-1-2n)2=(n+2)(2n+n2n-1)2nKf(Qn)+2n-1+n222n-3-22n-1=(n+2)(2n+n2n-1)×∑i=1n‍Cni2i+2n-1+n222n-3-22n-1.
Thus, the results of the Theorem 12 hold.


## 3.4. The Kirchhoff Index in the Total Graph of Hypercubes Networkst(Qn)

The total graph of a graphG, denoted by t(G), is the graph whose vertices correspond to the union of the set of vertices and edges of G, with two vertices of t(G) being adjacent if and only if the corresponding elements are adjacent or incident in G. We now proved the formula of the Kirchhoff index in the total graph of the hypercubes networks t(Qn), denoted by Kf(t(Qn)).Theorem 13.
Lett(Qn) be the total graphs of the hypercubes networks Qn with n≥2; then
(35)Kf(t(Qn))=2n-1(n+2)2n+3∑i=1n‍Cni2i+n4-4n28(n+1)+n2+(n2+2n)(n+4)2(n+3)∑i=1n‍Cni2i+3+n,
where the 2i(i=0,1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.Proof.
Let(36)Pt(Qn)(x)=x2n+a1x2n-1+a2x2n-2+…+a2n-1x.
Then by Lemma 8,
(37)Kf(t(Qn))2n=-a2n-2a2n-1.
Applying Lemma 6, the Laplacian characteristic polynomial of t(Qn) is
(38)Pt(Qn)(x)=x(x-n-2)(x-2n-2)q-pPt(Qn)(x)=×∏i=12n-1‍{[x2-2x-nx]+[3-2x+n]λi+λi2}Pt(Qn)(x)=x(x-n-2)(x-2n-2)q-pPt(Qn)(x)=×∏i=12n-1‍[x2-(2+n+2λi)x+λi2+(n+3)λi].
Consider that Qn has 2n vertices and r=n, by Lemma 7, we can get the following equality,
(39)Kf(t(Qn))=(r+2)22(r+3)Kf(Qn)+n2(r2-4)8(r+1)+n2Kf(t(Qn))=+n(r+2)(r+4)2(r+3)∑i=12n-1‍1λi+3+rKf(t(Qn))=(n+2)22(n+3)Kf(Qn)+n4-4n28(n+1)+n2Kf(t(Qn))=+(n2+2n)(n+4)2(n+3)∑i=12n-1‍1λi+3+n.
Consequently, the relationships between the hypercubes networks Qn and its variant networks t(Qn) for Kirchhoff index is
(40)Kf(t(Qn))=(n+2)22(n+3)Kf(Qn)+n4-4n28(n+1)+n2Kf(t(Qn))=+(n2+2n)(n+4)2(n+3)∑i=12n-1‍1λi+3+n.
Substitutes the result of Theorem 9 and simplifies about equation, we can get the formula for the Kirchhoff index on the total graph of hypercubes networks Kf(t(Qn)) as follows.
(41)Kf(t(Qn))=(n+2)22(n+3)Kf(Qn)+n4-4n28(n+1)+n2Kf(t(Qn))=+(n2+2n)(n+4)2(n+3)∑i=12n-1‍1λi+3+nKf(t(Qn))=2n-1(n+2)2n+3∑i=1n‍Cni2i+n4-4n28(n+1)+n2Kf(t(Qn))=+(n2+2n)(n+4)2(n+3)∑i=1n‍Cni2i+3+n.
This completes the proof of the Theorem.


## 4. Conclusions

In this paper, we focused on the Kirchhoff index of the hypercubes networks and related networks, which are important networks topology indexes for parallel processing computer systems. We obtained some exact formulae for the Kirchhoff index of the hypercubes networksQn and related networks by utilizing spectral graph theory, such as Kf(Qn)=2n∑i=1n‍(Cni/2i), where the 2i(i=1,…,n) are the eigenvalues of the Laplacian matrix of hypercubes networks and the binomial coefficients Cni are the multiplicities of the eigenvalues 2i.We also obtained the relationship for Kirchhoff index between hypercubes networksQn and its three variant networks l(Qn), s(Qn), and t(Qn), respectively, by deducing the characteristic polynomial of the Laplacian matrix related networks.Finally, the special formulae for the Kirchhoff indexes ofl(Qn), s(Qn), and t(Qn) were proposed, respectively, by making use of spectral graph theory and Vieta’s Theorem.



---

*Source: 543189-2013-12-12.xml*