# The Kirchhoff Index of Folded Hypercubes and Some Variant Networks

Authors: Jiabao Liu; Xiang-Feng Pan; Yi Wang; Jinde Cao
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Then-dimensional folded hypercube FQn is an important and attractive variant of the n-dimensional hypercube Qn, which is obtained from Qn by adding an edge between any pair of vertices complementary edges. FQn is superior to Qn in many measurements, such as the diameter of FQnwhich is ⌈n/2⌉, about a half of the diameter in terms of Qn. The Kirchhoff index Kf(G) is the sum of resistance distances between all pairs of vertices in G. In this paper, we established the relationships between the folded hypercubes networks FQn and its three variant networks l(FQn), s(FQn), and t(FQn) on their Kirchhoff index, by deducing the characteristic polynomial of the Laplacian matrix in spectral graph theory. Moreover, the explicit formulae for the Kirchhoff indexes of FQn, l(FQn), s(FQn), and t(FQn) were proposed, respectively.


---

## Body

## 1. Introduction

It is well known that interconnection networks play an important role in parallel communication systems. An interconnection network is usually modelled by connected graphsG=(V,E), where V denotes the set of processors and E denotes the set of communication links between processors in networks. In this work, we are concerned with finite undirected connected simple graphs (networks). For the graph theoretical definitions and notations, we follow [1].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, we refer to [1].LetG be a graph with vertices labelled 1,2,…,n. The resistance distances between vertices i and j, denoted by rij, are defined to be the effective electrical resistance between them if each edge of G is replaced by a unit resistor [2]. A famous distance-based topological index as the Kirchhoff index Kf(G), is defined as the sum of resistance distances between all pairs of vertices in G. Define
(1)Kf(G)=12∑i=1n‍∑j=1n‍rij(G),
known as the Kirchhoff index of G [2].The Kirchhoff index attracted extensive attention due to its wide applications in physics, chemistry, graph theory, and so forth [3–6]. For example, Zhu et al. [7] and Gutman and Mohar [8] proved that relations between Kirchhoff index of a graph and Laplacian eigenvalues of the graph. The Kirchhoff index also is a structure descriptor [9].However, it is difficult to design some algorithms [7, 10, 11] to calculate resistance distances and the Kirchhoff indexes of graphs. Hence, it makes sense to find explicit closed form for some special classes of graphs, for instance, the Kirchhoff index for cycles and complete graphs [12] which has been computed, geodetic graphs [13], some composite graphs [14], and composite networks [15]. Besides, many efforts were also made to obtain the Kirchhoff index bounds for some graphs [11, 16] and characterize extremal graphs as well, such as bicyclic graphs and cacti graphs [6, 17]. Details on its theory can be found in recent papers [11, 16, 17] and the references cited therein.The hypercubeQn is one of the most popular and efficient interconnection networks due to its excellent performance for some practical applications. There is a large amount of literature on the properties of hypercubes networks [18–20].As an important variant ofQn, the folded hypercube networks FQn, proposed by El-Amawy and Latifi [18], are the graph obtained from Qn by adding an edge between any pair of vertices complementary addresses. The folded hypercube FQn, in which diameter of FQn is ⌈n/2⌉, about half the diameter of Qn, has the same number of vertices as a hypercube Qn and 2n-1 edges more than hypercube; at the same time, the folded hypercubes preserve the symmetric properties of the hypercubes. The folded hypercubes FQn obtained considerable attention due to its perfect properties, such as symmetry, regular structure, strong connectivity, and small diameter, and many of its properties have been explored [21–26].But few works appear on the Kirchhoff index for the combinatorial networks, such as hypercubesQn and folded hypercubes FQn, except that Palacios and Renom [11] studied the bounds of the Kirchhoff index of hypercubes Qn by using probabilistic tools in 2010. In present paper, we established the relationships between the folded hypercubes networks FQn and three variant networks l(FQn), s(FQn), and t(FQn) on their Kirchhoff index, by deducing the characteristic polynomial of the Laplacian matrix in spectral graph theory.Recall the definitions of n-dimensional folded hypercubes networksFQn as follows [18].Definition 1 (see [18]).
The folded hypercubesFQn can be constructed from Qn by adding an edge to every pair of vertices with complementary addresses. Two vertices X=x1x2⋯xn and X¯=x1¯x2¯⋯xn¯ are adjacent in the folded hypercubes FQn.From above definition ofFQn, it is easy to get that the folded hypercubes FQn have 2n vertices and (n+1)2n-1 edges, respectively.The line graph of a graphG, denoted by l(G), is the graph whose vertices correspond to the edges of G with two vertices of L(G) being adjacent if and only if the corresponding edges in G share a common vertex. The subdivision graph of a graph G, denoted by s(G), is the graph obtained by replacing every edge in G with a copy of P2 (path of length two). The total graph of a graph G, 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.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 above results, we present the corresponding calculated formulae for the Kirchhoff index of the hypercubes networks Qn and its three-variant networks l(FQn), s(FQn), and t(FQn) in this paper.The remainder of present 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 and some conclusions are given in Section 4, respectively.


## 2. Notations and Some Preliminaries

In this section, we introduced some basic properties which we need to use in the proofs of our main results.M. Chen and B. X. Chen have studied the Laplacian spectra of folded hypercubes networks in 2011 [21].Lemma 2 (see [21]).
For the folded hypercubes networksFQn with n≥2, the spectrum of Laplacian matrix in terms of hypercubes networks is as follows.
(
1
) If n≡0(mod⁡2),(2)Spec⁡(FQn)=(048⋯2n-82n-42nCnnCnn-1+Cnn-2Cnn-3+Cnn-4⋯Cn5+Cn4Cn3+Cn2Cn1+Cn0).
(
2
) If n≡1(mod⁡2),(3)Spec⁡(FQn)=(048⋯2n-62n-22n+2Cn0Cn1+Cn2Cn3+Cn4⋯Cnn-4+Cnn-3Cnn-2+Cnn-1Cnn),where Cni are the binomial coefficients; the elements in the first and second rows are the eigenvalues of the Laplacian matrix of folded hypercubes networks and the multiplicities of the corresponding eigenvalues.Lemma 3 (see [7, 8]).
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 4 (see [27]).
LetG be a 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 polynomial for the Laplacian matrix of graphs l(G), s(G), and t(G), respectively.It is worthwhile to note that the conclusion of Lemma4 is not completely correct; the authors [28] recently show the Laplacian characteristic polynomial of t(G), where G is a regular graph, which corrects Lemma 3 in Gao et al. [27] as follows.Lemma 5 (see [28]).
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 gives an expression onKf(t(G)) and Kf(G) of a regular graph G.Lemma 6 (see [28]).
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 for the Kirchhoff index on the subdivision graph of hypercubess(FQn), we prove the following lemma utilizing Vieta's theorem; in our proof, some techniques in [27] are referred.Lemma 7.
LetP(FQn)(x) be the characteristic polynomial of the Laplacian matrix of the folded hypercubes FQn with n≥2 and
(8)P(FQn)(x)=x2n+a1x2n-1+a2x2n-2+⋯+a2n-1x;
then,
(9)Kf⁡(FQn)2n=-a2n-2a2n-1,
where a2n-1,a2n-2 are the coefficient of x and x2 in the characteristic polynomial, respectively.Proof.
LetSpec(FQn)={λ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 that G is connected graph and the multiplicity of 0 as an eigenvalue of L(G) is equal to the number of the connected components in G. So a2n-1≠0, by Lemma 3 and Vieta's theorem,
(12)Kf(FQn)2n=∑i=12n-1‍1λi=-a2n-2a2n-1,
where a2n-1,a2n-2 are the coefficient of x and x2 in the characteristic polynomial of the Laplacian matrix of the hypercubes FQn.


## 3. Main Results

### 3.1. The Kirchhoff Index in Folded Hypercubes NetworksFQn

In this section, we firstly give formula for the Kirchhoff index of the folded hypercubesFQn with any positive integer n.Theorem 8.
For the folded hypercubes networksFQn with any positive integer n,
(13)(1)Kf⁡(FQn)=2n∑i=1n/2‍Cnn-i+Cnn-i-14i,hhhi=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf⁡(FQn)=2n∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+2n-1n+1,hhhhhhhi=1,2,…,n-12,ifn≡1(mod⁡2),
where the 4i, i=1,2,…,(n-1)/2 or n/2 are the eigenvalues of the Laplacian matrix of hypercubes networks FQn and Cni are the binomial coefficients,Proof.
The hypercubes networksFQn have 2n vertices and (n+1)2n-1 edges.
By Lemma3, if  n≡0(mod⁡2),(14)Spec⁡(FQn)=(048⋯2n-82n-42nCnnCnn-1+Cnn-2Cnn-3+Cnn-4⋯Cn5+Cn4Cn3+Cn2Cn1+Cn0),then
Kf(FQn)=2n∑i=12n-1‍1λi=2n(Cnn-1+Cnn-24×1+Cnn-3+Cnn-44×2+⋯hhhhhhh+Cnn-i+Cnn-i-14×i+⋯+Cn1+C04×(n/2))=2n∑i=1n/2‍Cnn-i+Cnn-i-14i,hhhhhhhhi=1,2,…,n2.
By Lemma3, if  n≡1(mod⁡2),(16)Spec⁡(FQn)=(048⋯2n-62n-22n+2Cn0Cn1+Cn2Cn3+Cn4⋯Cnn-4+Cnn-3Cnn-2+Cnn-1Cnn),then
(17)Kf(FQn)=2n∑i=12n-1‍1λi=2n(Cn1+Cn24×1+Cn3+Cn44×2+⋯+Cn2i+Cn2i-14×i+⋯hhhhhhh+Cnn-2+Cn-14×((n-1)/2)+Cnn2n+2)=2n∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+2n-1n+1,hhhhhhhhhhhhhhi=1,2,…,n-12.
The proof of Theorem 8 is completed.


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

In the following theorem, we proposed the formula for calculating the Kirchhoff index, denoted byKf(l(FQn)), on the line graph of folded hypercubes l(FQn).Theorem 9.
Letl(FQn) be line graphs of hypercubes FQn with any positive integer n; then
(18)(1)Kf⁡(l(FQn))=(n+1)2n-1∑i=1n/2‍Cnn-i+Cnn-i-14i+(n-1)22n-3,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf⁡(l(FQn))=(n+1)2n-1∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+(n-1)22n-3+2n-2,i=1,2,…,n-12,ifn≡1(mod⁡2),
where the 4i, i=1,2,…,(n-1)/2 or n/2 are the eigenvalues of the Laplacian matrix of folded hypercubes networks FQn and Cni are the binomial coefficients.Proof.
Now for convenience, we denote the numbers of vertices and edges in the folded hypercubes networksFQn by p=2n and q=(n+1)2n-1, respectively.
By Lemma4,
(19)Pl(FQn)(x)=(x-2r)q-pPFQn(x).
Notice that folded hypercubes networks FQn are regular graphs with the degree of any vertex being r=n+1; compare the spectrum of FQn as follows.
(
1
) If n≡0(mod⁡2),(20)Spec⁡(FQn)=(048⋯2n-82n-42nCnnCnn-1+Cnn-2Cnn-3+Cnn-4⋯Cn5+Cn4Cn3+Cn2Cn1+Cn0).(2) If n≡1(mod⁡2),(21)Spec⁡(FQn)=(048⋯2n-62n-22n+2Cn0Cn1+Cn2Cn3+Cn4⋯Cnn-4+Cnn-3Cnn-2+Cnn-1Cnn).
We can easily obtain the spectrum ofl(FQn) as follows.
(
1
) If n≡0(mod⁡2),(22)Spec⁡(l(FQn))=(2r048⋯2n-82n-42nq-pCnnCnn-1+Cnn-2Cnn-3+Cnn-4⋯Cn5+Cn4Cn3+Cn2Cn1+Cn0).(2) If n≡1(mod⁡2),(23)Spec⁡(l(FQn))=(2r048⋯2n-62n-22n+2q-pCn0Cn1+Cn2Cn3+Cn4⋯Cnn-4+Cnn-3Cnn-2+Cnn-1Cnn),where λ0,λ1,…,λn,λn+1,…,λ2n-1 are the eigenvalues of FQn and λ0≤λ1≤λ2≤⋯≤λn≤λn+1≤⋯≤λ2n-1.
By Lemma4,
(24)Kf(l(FQn))(n+1)2n-1=∑i=12n-1‍1λi+(n+1)2n-1-2n2r=Kf(FQn)2n+(n+1)2n-1-2n2n+2=Kf(FQn)2n-2n-1n+1+2n-2.
Therefore, we clearly obtained
(25)Kf(l(FQn))=(n+1)2n-1(Kf(FQn)2n-2n-1n+1+2n-2)=n+12Kf(FQn)+n22n-3-22n-3=n+12Kf(FQn)+(n-1)22n-3.
Substituting the results of Theorem 8 into (25), we can get the formula for the Kirchhoff index on the line graph of folded hypercubes Kf(l(FQn)):
(26)(1)Kf(l(FQn))=(n+1)2n-1∑i=1n/2‍Cnn-i+Cnn-i-14i+(n-1)22n-3,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf(l(FQn))=(n+1)2n-1∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+(n-1)22n-3+2n-2,i=1,2,…,n-12,ifn≡1(mod⁡2),
which completes the proof.


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

In an almost identical way as Theorem9, we derived the formula for the Kirchhoff index on the subdivision graph of folded hypercubes s(FQn), denoted by Kf(s(FQn)).Theorem 10.
Lets(FQn) be subdivision graphs of the folded hypercubes FQn with any positive integer n; then,
(27)(1)Kf⁡(s(FQn))=(n+3)22n-1∑i=1n/2‍Cnn-i+Cnn-i-14i+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf⁡(s(FQn))=(n+3)22n-1×(∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+2n-1n+1)+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2,i=1,2,…,n-12,ifn≡1(mod⁡2).Proof.
Now suppose thatPs(FQn)(x) is the characteristic polynomial of the Laplacian matrix of the s(FQn); let Ps(FQn)(x)=x2n+a1x2n-1+a2x2n-2+⋯+a2n-1x and
(28)Spec⁡(s(FQn))={λ0,λ1,λ2,…,λn,λn+1,…,λ2n-1},
where λi,i=0,1,2,…,2n-1, are the Laplacian eigenvalues of s(FQn).
Then, by Lemma7,
(29)Kf(s(FQn))2n=-a2n-2a2n-1.
By Lemma 5,
(30)Ps(FQn)(x)=(-1)2n(2-x)(n+1)2n-1-2n×[x2n(r+2-x)2n+a1x2n-1(r+2-x)2n-1+⋯+a2n-2x2(r+2-x)2+a2n-1x(r+2-x)].
Consequently, the coefficient ofx2 in Ps(FQn)(x) is
(31)(-1)2n{2(n+1)2n-1-2na2n-2(r+2)2-2(n+1)2n-1-2na2n-1-[(n+1)2n-1-2n]×2(n+1)2n-1-2n-1(r+2)a2n-1},
and the coefficient of x in Ps(FQn)(x) is
(32)(-1)2n2(n+1)2n-1-2n(r+2)a2n-1.
Since s(FQn) has 2n+(n+1)2n-1 vertices. For convenience, denote p=2n, q=(n+1)2n-1, and r=n+1, respectively. By Lemma 7 and substituting the coefficients into (12), we get
(33)Kf(s(FQn))p+q=-2q-p(r+2)2-2q-pa2n-12q-pa2n-1(r+2)-(q-p)2q-p-1a2n-1(r+2)2q-pa2n-1(r+2)(34)=-a2n-2(r+2)a2n-1+1r+2+q-p2.
Combining the results of Lemma 7 and (34),
(35)Kf(s(FQn))p+q=(r+2)Kf(FQn)2n+1r+2+q-p2.
Hence,
(36)Kf(s(FQn))=(p+q)(r+2)Kf(FQn)2n+p+qr+2+q2-p22.
Simplifying (36) by substituting p=2n,q=(n+1)2n-1, and r=n+1, we can get
(37)Kf(s(FQn))=[2n+(n+1)2n-1](n+3)Kf(FQn)2n+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2=(n+3)22Kf(FQn)+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2.
Note that the results of Theorem8 and (37), we can get the formulae for the Kirchhoff index of the subdivision graph of the folded hypercubes Kf(s(FQn)):
(38)(1)Kf(s(FQn))=(n+3)22n-1∑i=1n/2‍Cnn-i+Cnn-i-14i+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf(s(FQn))=(n+3)22n-1×(∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+2n-1n+1)+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2,i=1,2,…,n-12,ifn≡1(mod⁡2),
which completes the proof.


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

We now proved the formula for the Kirchhoff index in the total graph of the folded hypercubest(FQn), denoted by Kf(t(FQn)).Theorem 11.
Lett(FQn) be the total graphs of the folded hypercubes networks FQn with any positive integer n; then,
(1)Kf⁡(t(FQn))=2n-1(n+3)2n+4∑i=1n/2‍Cnn-i+Cnn-i-14i+22n-3(n-1)(n+3)n+2+2n-1+2n-1(n+3)(n+5)n+4∑i=1n/2‍Cnn-i+Cnn-i-14i+n+4,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf⁡(t(FQn))=2n-1(n+3)2n+4×(∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+12n+2)+22n-3(n-1)(n+3)n+2+2n-1+2n-1(n+3)(n+5)n+4∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+n+4,i=1,2,…,n-12,ifn≡1(mod⁡2),
where the 4i,i=1,2,…,(n-1)/2 or n/2, are the eigenvalues of the Laplacian matrix of folded hypercubes networks FQn and Cni are the binomial coefficients.Proof.
LetPt(FQn)(x)=x2n+a1x2n-1+a2x2n-2+⋯+a2n-1x and
(40)Spec(t(FQn))={λ0,λ1,λ2,…λn,λn+1,…,λ2n-1},
where λi,i=0,1,2,…,2n-1, are the Laplacian eigenvalues of FQn.
Applying Lemma5, the Laplacian characteristic polynomial of t(FQn) is
(41)Pt(FQn)(x)=x(x-n-3)(x-2n-4)q-p×∏i=12n-1‍{λi2[x2-2x-(n+1)x]hhhhhh+[3-2x+(n+1)]λi+λi2}=x(x-n-3)(x-2n-4)q-p×∏i=12n-1‍[x2-(3+n+2λi)x+λi2+(n+4)λi].
Notice thatt(FQn) has 2n+(n+1)2n-1 vertices, that is, p+q vertices. By Lemma 6, we can get the following:
(42)Kf(t(FQn))=(r+2)22(r+3)Kf(FQn)+n2(r2-4)8(r+1)+n2iiiiiiiiiiiiiiiiiii+n(r+2)(r+4)2(r+3)∑i=12n-1‍1λi+3+r.
Consider that FQn has 2n vertices and r=n+1, we have
(43)Kf(t(FQn))=(n+3)22(n+4)Kf(FQn)iiiiiiiiiiiiiiiiiiiiii+4n[(n+1)2-4]8(n+2)+2n-1iiiiiiiiiiiiiiiiiiiiii+2n(n+3)(n+5)2(n+4)∑i=12n-1‍1λi+n+4Kf(t(FQn))=(n+3)22(n+4)Kf(FQn)iiiiiiiiiiiiiiiiiiiiii+22n-3(n-1)(n+3)n+2+2n-1iiiiiiiiiiiiiiiiiiiiii+2n-1(n+3)(n+5)n+4∑i=12n-1‍1λi+n+4.
From (43), the relationships between the folded hypercubes networks FQn and its variant networks t(FQn) for Kirchhoff index are as follows:
(44)Kf(t(FQn))=(n+3)22(n+4)Kf(FQn)Kf(t(FQn))+22n-3(n-1)(n+3)n+2+2n-1Kf(t(FQn))+2n-1(n+3)(n+5)n+4∑i=12n-1‍1λi+n+4.
Substituting results of Theorem8 into (44) and simplifying (44), we can get the formula for the Kirchhoff index on the total graph of folded hypercubes Kf(t(FQn)); we consider two cases in terms of if  n≡0(mod⁡2) and ifn≡1(mod⁡2),
(45)(1)Kf(t(FQn))=2n-1(n+3)2n+4∑i=1n/2‍Cnn-i+Cnn-i-14i+22n-3(n-1)(n+3)n+2+2n-1+2n-1(n+3)(n+5)n+4∑i=1n/2‍Cnn-i+Cnn-i-14i+n+4,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf(t(FQn))=2n-1(n+3)2n+4×(∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+12n+2)+22n-3(n-1)(n+3)n+2+2n-1+2n-1(n+3)(n+5)n+4∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+n+4,i=1,2,…,n-12,ifn≡1(mod⁡2),
where the 4i, i=1,2,…,(n-1)/2 or n/2, are the eigenvalues of the Laplacian matrix of folded hypercubes networks FQn and Cni are the binomial coefficients.
This completes the proof of Theorem11.Remark 12.
The authors [27] gave the formulae for the Kirchhoff index of l(G), s(G), and t(G), where G is a regular graph. In this paper, we proposed the special formulae for calculating the Kirchhoff indexes of the folded hypercubes networks FQn and its three variant networks l(FQn), s(FQn), and t(FQn), respectively, which enhanced related results on the Kirchhoff index.


## 3.1. The Kirchhoff Index in Folded Hypercubes NetworksFQn

In this section, we firstly give formula for the Kirchhoff index of the folded hypercubesFQn with any positive integer n.Theorem 8.
For the folded hypercubes networksFQn with any positive integer n,
(13)(1)Kf⁡(FQn)=2n∑i=1n/2‍Cnn-i+Cnn-i-14i,hhhi=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf⁡(FQn)=2n∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+2n-1n+1,hhhhhhhi=1,2,…,n-12,ifn≡1(mod⁡2),
where the 4i, i=1,2,…,(n-1)/2 or n/2 are the eigenvalues of the Laplacian matrix of hypercubes networks FQn and Cni are the binomial coefficients,Proof.
The hypercubes networksFQn have 2n vertices and (n+1)2n-1 edges.
By Lemma3, if  n≡0(mod⁡2),(14)Spec⁡(FQn)=(048⋯2n-82n-42nCnnCnn-1+Cnn-2Cnn-3+Cnn-4⋯Cn5+Cn4Cn3+Cn2Cn1+Cn0),then
Kf(FQn)=2n∑i=12n-1‍1λi=2n(Cnn-1+Cnn-24×1+Cnn-3+Cnn-44×2+⋯hhhhhhh+Cnn-i+Cnn-i-14×i+⋯+Cn1+C04×(n/2))=2n∑i=1n/2‍Cnn-i+Cnn-i-14i,hhhhhhhhi=1,2,…,n2.
By Lemma3, if  n≡1(mod⁡2),(16)Spec⁡(FQn)=(048⋯2n-62n-22n+2Cn0Cn1+Cn2Cn3+Cn4⋯Cnn-4+Cnn-3Cnn-2+Cnn-1Cnn),then
(17)Kf(FQn)=2n∑i=12n-1‍1λi=2n(Cn1+Cn24×1+Cn3+Cn44×2+⋯+Cn2i+Cn2i-14×i+⋯hhhhhhh+Cnn-2+Cn-14×((n-1)/2)+Cnn2n+2)=2n∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+2n-1n+1,hhhhhhhhhhhhhhi=1,2,…,n-12.
The proof of Theorem 8 is completed.


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

In the following theorem, we proposed the formula for calculating the Kirchhoff index, denoted byKf(l(FQn)), on the line graph of folded hypercubes l(FQn).Theorem 9.
Letl(FQn) be line graphs of hypercubes FQn with any positive integer n; then
(18)(1)Kf⁡(l(FQn))=(n+1)2n-1∑i=1n/2‍Cnn-i+Cnn-i-14i+(n-1)22n-3,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf⁡(l(FQn))=(n+1)2n-1∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+(n-1)22n-3+2n-2,i=1,2,…,n-12,ifn≡1(mod⁡2),
where the 4i, i=1,2,…,(n-1)/2 or n/2 are the eigenvalues of the Laplacian matrix of folded hypercubes networks FQn and Cni are the binomial coefficients.Proof.
Now for convenience, we denote the numbers of vertices and edges in the folded hypercubes networksFQn by p=2n and q=(n+1)2n-1, respectively.
By Lemma4,
(19)Pl(FQn)(x)=(x-2r)q-pPFQn(x).
Notice that folded hypercubes networks FQn are regular graphs with the degree of any vertex being r=n+1; compare the spectrum of FQn as follows.
(
1
) If n≡0(mod⁡2),(20)Spec⁡(FQn)=(048⋯2n-82n-42nCnnCnn-1+Cnn-2Cnn-3+Cnn-4⋯Cn5+Cn4Cn3+Cn2Cn1+Cn0).(2) If n≡1(mod⁡2),(21)Spec⁡(FQn)=(048⋯2n-62n-22n+2Cn0Cn1+Cn2Cn3+Cn4⋯Cnn-4+Cnn-3Cnn-2+Cnn-1Cnn).
We can easily obtain the spectrum ofl(FQn) as follows.
(
1
) If n≡0(mod⁡2),(22)Spec⁡(l(FQn))=(2r048⋯2n-82n-42nq-pCnnCnn-1+Cnn-2Cnn-3+Cnn-4⋯Cn5+Cn4Cn3+Cn2Cn1+Cn0).(2) If n≡1(mod⁡2),(23)Spec⁡(l(FQn))=(2r048⋯2n-62n-22n+2q-pCn0Cn1+Cn2Cn3+Cn4⋯Cnn-4+Cnn-3Cnn-2+Cnn-1Cnn),where λ0,λ1,…,λn,λn+1,…,λ2n-1 are the eigenvalues of FQn and λ0≤λ1≤λ2≤⋯≤λn≤λn+1≤⋯≤λ2n-1.
By Lemma4,
(24)Kf(l(FQn))(n+1)2n-1=∑i=12n-1‍1λi+(n+1)2n-1-2n2r=Kf(FQn)2n+(n+1)2n-1-2n2n+2=Kf(FQn)2n-2n-1n+1+2n-2.
Therefore, we clearly obtained
(25)Kf(l(FQn))=(n+1)2n-1(Kf(FQn)2n-2n-1n+1+2n-2)=n+12Kf(FQn)+n22n-3-22n-3=n+12Kf(FQn)+(n-1)22n-3.
Substituting the results of Theorem 8 into (25), we can get the formula for the Kirchhoff index on the line graph of folded hypercubes Kf(l(FQn)):
(26)(1)Kf(l(FQn))=(n+1)2n-1∑i=1n/2‍Cnn-i+Cnn-i-14i+(n-1)22n-3,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf(l(FQn))=(n+1)2n-1∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+(n-1)22n-3+2n-2,i=1,2,…,n-12,ifn≡1(mod⁡2),
which completes the proof.


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

In an almost identical way as Theorem9, we derived the formula for the Kirchhoff index on the subdivision graph of folded hypercubes s(FQn), denoted by Kf(s(FQn)).Theorem 10.
Lets(FQn) be subdivision graphs of the folded hypercubes FQn with any positive integer n; then,
(27)(1)Kf⁡(s(FQn))=(n+3)22n-1∑i=1n/2‍Cnn-i+Cnn-i-14i+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf⁡(s(FQn))=(n+3)22n-1×(∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+2n-1n+1)+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2,i=1,2,…,n-12,ifn≡1(mod⁡2).Proof.
Now suppose thatPs(FQn)(x) is the characteristic polynomial of the Laplacian matrix of the s(FQn); let Ps(FQn)(x)=x2n+a1x2n-1+a2x2n-2+⋯+a2n-1x and
(28)Spec⁡(s(FQn))={λ0,λ1,λ2,…,λn,λn+1,…,λ2n-1},
where λi,i=0,1,2,…,2n-1, are the Laplacian eigenvalues of s(FQn).
Then, by Lemma7,
(29)Kf(s(FQn))2n=-a2n-2a2n-1.
By Lemma 5,
(30)Ps(FQn)(x)=(-1)2n(2-x)(n+1)2n-1-2n×[x2n(r+2-x)2n+a1x2n-1(r+2-x)2n-1+⋯+a2n-2x2(r+2-x)2+a2n-1x(r+2-x)].
Consequently, the coefficient ofx2 in Ps(FQn)(x) is
(31)(-1)2n{2(n+1)2n-1-2na2n-2(r+2)2-2(n+1)2n-1-2na2n-1-[(n+1)2n-1-2n]×2(n+1)2n-1-2n-1(r+2)a2n-1},
and the coefficient of x in Ps(FQn)(x) is
(32)(-1)2n2(n+1)2n-1-2n(r+2)a2n-1.
Since s(FQn) has 2n+(n+1)2n-1 vertices. For convenience, denote p=2n, q=(n+1)2n-1, and r=n+1, respectively. By Lemma 7 and substituting the coefficients into (12), we get
(33)Kf(s(FQn))p+q=-2q-p(r+2)2-2q-pa2n-12q-pa2n-1(r+2)-(q-p)2q-p-1a2n-1(r+2)2q-pa2n-1(r+2)(34)=-a2n-2(r+2)a2n-1+1r+2+q-p2.
Combining the results of Lemma 7 and (34),
(35)Kf(s(FQn))p+q=(r+2)Kf(FQn)2n+1r+2+q-p2.
Hence,
(36)Kf(s(FQn))=(p+q)(r+2)Kf(FQn)2n+p+qr+2+q2-p22.
Simplifying (36) by substituting p=2n,q=(n+1)2n-1, and r=n+1, we can get
(37)Kf(s(FQn))=[2n+(n+1)2n-1](n+3)Kf(FQn)2n+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2=(n+3)22Kf(FQn)+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2.
Note that the results of Theorem8 and (37), we can get the formulae for the Kirchhoff index of the subdivision graph of the folded hypercubes Kf(s(FQn)):
(38)(1)Kf(s(FQn))=(n+3)22n-1∑i=1n/2‍Cnn-i+Cnn-i-14i+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf(s(FQn))=(n+3)22n-1×(∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+2n-1n+1)+2n+(n+1)2n-1n+3+(n+1)24n-1-4n2,i=1,2,…,n-12,ifn≡1(mod⁡2),
which completes the proof.


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

We now proved the formula for the Kirchhoff index in the total graph of the folded hypercubest(FQn), denoted by Kf(t(FQn)).Theorem 11.
Lett(FQn) be the total graphs of the folded hypercubes networks FQn with any positive integer n; then,
(1)Kf⁡(t(FQn))=2n-1(n+3)2n+4∑i=1n/2‍Cnn-i+Cnn-i-14i+22n-3(n-1)(n+3)n+2+2n-1+2n-1(n+3)(n+5)n+4∑i=1n/2‍Cnn-i+Cnn-i-14i+n+4,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf⁡(t(FQn))=2n-1(n+3)2n+4×(∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+12n+2)+22n-3(n-1)(n+3)n+2+2n-1+2n-1(n+3)(n+5)n+4∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+n+4,i=1,2,…,n-12,ifn≡1(mod⁡2),
where the 4i,i=1,2,…,(n-1)/2 or n/2, are the eigenvalues of the Laplacian matrix of folded hypercubes networks FQn and Cni are the binomial coefficients.Proof.
LetPt(FQn)(x)=x2n+a1x2n-1+a2x2n-2+⋯+a2n-1x and
(40)Spec(t(FQn))={λ0,λ1,λ2,…λn,λn+1,…,λ2n-1},
where λi,i=0,1,2,…,2n-1, are the Laplacian eigenvalues of FQn.
Applying Lemma5, the Laplacian characteristic polynomial of t(FQn) is
(41)Pt(FQn)(x)=x(x-n-3)(x-2n-4)q-p×∏i=12n-1‍{λi2[x2-2x-(n+1)x]hhhhhh+[3-2x+(n+1)]λi+λi2}=x(x-n-3)(x-2n-4)q-p×∏i=12n-1‍[x2-(3+n+2λi)x+λi2+(n+4)λi].
Notice thatt(FQn) has 2n+(n+1)2n-1 vertices, that is, p+q vertices. By Lemma 6, we can get the following:
(42)Kf(t(FQn))=(r+2)22(r+3)Kf(FQn)+n2(r2-4)8(r+1)+n2iiiiiiiiiiiiiiiiiii+n(r+2)(r+4)2(r+3)∑i=12n-1‍1λi+3+r.
Consider that FQn has 2n vertices and r=n+1, we have
(43)Kf(t(FQn))=(n+3)22(n+4)Kf(FQn)iiiiiiiiiiiiiiiiiiiiii+4n[(n+1)2-4]8(n+2)+2n-1iiiiiiiiiiiiiiiiiiiiii+2n(n+3)(n+5)2(n+4)∑i=12n-1‍1λi+n+4Kf(t(FQn))=(n+3)22(n+4)Kf(FQn)iiiiiiiiiiiiiiiiiiiiii+22n-3(n-1)(n+3)n+2+2n-1iiiiiiiiiiiiiiiiiiiiii+2n-1(n+3)(n+5)n+4∑i=12n-1‍1λi+n+4.
From (43), the relationships between the folded hypercubes networks FQn and its variant networks t(FQn) for Kirchhoff index are as follows:
(44)Kf(t(FQn))=(n+3)22(n+4)Kf(FQn)Kf(t(FQn))+22n-3(n-1)(n+3)n+2+2n-1Kf(t(FQn))+2n-1(n+3)(n+5)n+4∑i=12n-1‍1λi+n+4.
Substituting results of Theorem8 into (44) and simplifying (44), we can get the formula for the Kirchhoff index on the total graph of folded hypercubes Kf(t(FQn)); we consider two cases in terms of if  n≡0(mod⁡2) and ifn≡1(mod⁡2),
(45)(1)Kf(t(FQn))=2n-1(n+3)2n+4∑i=1n/2‍Cnn-i+Cnn-i-14i+22n-3(n-1)(n+3)n+2+2n-1+2n-1(n+3)(n+5)n+4∑i=1n/2‍Cnn-i+Cnn-i-14i+n+4,i=1,2,…,n2,ifn≡0(mod⁡2);(2)Kf(t(FQn))=2n-1(n+3)2n+4×(∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+12n+2)+22n-3(n-1)(n+3)n+2+2n-1+2n-1(n+3)(n+5)n+4∑i=1(n-1)/2‍Cn2i-1+Cn2i4i+n+4,i=1,2,…,n-12,ifn≡1(mod⁡2),
where the 4i, i=1,2,…,(n-1)/2 or n/2, are the eigenvalues of the Laplacian matrix of folded hypercubes networks FQn and Cni are the binomial coefficients.
This completes the proof of Theorem11.Remark 12.
The authors [27] gave the formulae for the Kirchhoff index of l(G), s(G), and t(G), where G is a regular graph. In this paper, we proposed the special formulae for calculating the Kirchhoff indexes of the folded hypercubes networks FQn and its three variant networks l(FQn), s(FQn), and t(FQn), respectively, which enhanced related results on the Kirchhoff index.


## 4. Conclusions

The main purpose of this paper is to investigate the Kirchhoff index of the folded hypercubes networks and related networks, which are important networks topology indexes for parallel processing computer systems. We established the relationships between the folded hypercubes networksFQn and its three variant networks l(FQn), s(FQn), and t(FQn) for their Kirchhoff index, respectively, by deducing the characteristic polynomial of the Laplacian matrix related networks.Moreover, the explicit formulae were proposed for calculating the Kirchhoff indexes ofFQn, l(FQn), s(FQn), and t(FQn), respectively, by making use of the characteristic polynomial of the Laplacian matrix in spectral graph theory and Vieta's theorem.



---

*Source: 380874-2014-01-16.xml*