The Kirchhoff Index of Some Combinatorial Networks

Abstract

The Kirchhoff index Kf( G ) is the sum of the effective resistance distances between all pairs of vertices in G . The hypercube [subscript] Q n [/subscript] and the folded hypercube F [subscript] Q n [/subscript] are well known networks due to their perfect properties. The graph [superscript] G [low *] [/superscript] , constructed from G , is the line graph of the subdivision graph S ( G ) . In this paper, explicit formulae expressing the Kirchhoff index of ( [subscript] Q n [/subscript] [superscript] ) [low *] [/superscript] and ( F [subscript] Q n [/subscript] [superscript] ) [low *] [/superscript] are found by deducing the characteristic polynomial of the Laplacian matrix of [superscript] G [low *] [/superscript] in terms of that of G .

Jia-Bao Liu 1, 2, 3 and Xiang-Feng Pan 2 and Jinde Cao 3, 4 and Fu-Tao Hu 2

Academic Editor:Carmen Coll

1, Department of Public Courses, Anhui Xinhua University, Hefei 230088, China
2, School of Mathematical Sciences, Anhui University, Hefei 230601, China
3, Department of Mathematics, Southeast University, Nanjing 210096, China
4, Department of Mathematics, Faculty of Science, King Abdulaziz University, Jeddah 21589, Saudi Arabia

Received 7 December 2014; Revised 6 March 2015; Accepted 12 March 2015; 1 October 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

It is well known that interconnection networks play an important role in parallel communication systems. An interconnection network is usually modelled by a connected graph [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] denotes the set of processors and [figure omitted; refer to PDF] denotes the set of communication links between processors in networks. The hypercube [figure omitted; refer to PDF] and the folded hypercube [figure omitted; refer to PDF] are two very popular and efficient interconnection networks due to their excellent performance in some practical applications. The symmetry, regular structure, strong connectivity, small diameter, and many of their properties have been explored [1-5].

The adjacency matrix [figure omitted; refer to PDF] of [figure omitted; refer to PDF] is an [figure omitted; refer to PDF] matrix with the [figure omitted; refer to PDF] -entry equal to 1 if vertices [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are adjacent and to 0 if otherwise. Let [figure omitted; refer to PDF] be the degree diagonal matrix of [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] is called the Laplacian matrix of [figure omitted; refer to PDF] . Denote the Laplacian characteristic polynomial of [figure omitted; refer to PDF] by [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] are the coefficients of the Laplacian characteristic polynomial [6]. The eigenvalues of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are called eigenvalues and Laplacian eigenvalues of [figure omitted; refer to PDF] , respectively. In this paper we are concerned with some finite undirected connected simple graphs (networks). For the underlying graph, theoretical definitions, and notations, we follow [7].

Let [figure omitted; refer to PDF] be a graph with vertices labelled [figure omitted; refer to PDF] . It is well known that the standard distance between two vertices of [figure omitted; refer to PDF] , denoted by [figure omitted; refer to PDF] , is the shortest path connecting the two vertices. A novel distance function named resistance distance was firstly proposed by Klein and Randic [8]. The resistance distance between vertices [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , denoted by [figure omitted; refer to PDF] , is defined to be the effective electrical resistance between them if each edge of [figure omitted; refer to PDF] is replaced by a unit resistor [8]. A famous distance-based topological index as the Kirchhoff index, [figure omitted; refer to PDF] , is defined as the sum of resistance distances between all pairs of vertices in [figure omitted; refer to PDF] [8].

The Kirchhoff index has been attracting extensive attention due to its wide applications in physics, chemistry, graph theory, and so forth [9-18]. Details on its theory can be found in recent papers [19, 20] and the references cited therein. But there are only few works appearing on the Kirchhoff index in combinatorial networks. In the present paper, we establish the closed-form formulae expressing the Kirchhoff index of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , where the graph [figure omitted; refer to PDF] , constructed from [figure omitted; refer to PDF] , is the line graph of the subdivision graph [figure omitted; refer to PDF] .

The main purpose of this paper is to investigate the Kirchhoff index of some combinatorial networks. The graph [figure omitted; refer to PDF] , constructed from [figure omitted; refer to PDF] , is the line graph of the subdivision graph [figure omitted; refer to PDF] . We have established the relationships between [figure omitted; refer to PDF] , [figure omitted; refer to PDF] and their variant networks [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , in terms of Kirchhoff index, respectively. Moreover, explicit formulae have been proposed for expressing the Kirchhoff index of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] by making use of the characteristic polynomial of the Laplacian matrix in spectral graph theory.

The remainder of the paper is organized as follows. Section 2 provides some underlying definitions and preliminaries in our discussion. The proofs of main results and some examples are given in Sections 3 and 4, respectively.

2. Definitions and Preliminaries

In this section, we recall some underlying definitions and properties which we need to use in the proofs of our main results as follows.

Definition 1 (hypercube [figure omitted; refer to PDF] [21]).

The hypercube [figure omitted; refer to PDF] has [figure omitted; refer to PDF] vertices each labelled with a binary string of length [figure omitted; refer to PDF] . Two vertices [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are adjacent if and only if there exists an [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , such that [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] denoted the complement of binary digit [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , for all [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] .

Definition 2 (folded hypercube [figure omitted; refer to PDF] [2]).

The folded hypercube [figure omitted; refer to PDF] can be constructed from [figure omitted; refer to PDF] by adding an edge to every pair of vertices with complementary addresses. Two vertices [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are adjacent in the folded hypercube [figure omitted; refer to PDF] .

Definition 3 (construction of [figure omitted; refer to PDF] [22]).

Define the following operation of [figure omitted; refer to PDF] , constructing [figure omitted; refer to PDF] from [figure omitted; refer to PDF] , as follows [22]:

(i) Replace each vertex [figure omitted; refer to PDF] by [figure omitted; refer to PDF] , the complete graph on [figure omitted; refer to PDF] vertices.

(ii) There is an edge joining a vertex of [figure omitted; refer to PDF] and a vertex of [figure omitted; refer to PDF] in [figure omitted; refer to PDF] if and only if there is an edge joining [figure omitted; refer to PDF] and [figure omitted; refer to PDF] in [figure omitted; refer to PDF] .

(iii): For each vertex [figure omitted; refer to PDF] of [figure omitted; refer to PDF] , [figure omitted; refer to PDF] .

Recall the following two underlying conceptions that related to the above construction of [figure omitted; refer to PDF] . The subdivision graph [figure omitted; refer to PDF] of a graph [figure omitted; refer to PDF] is obtained from [figure omitted; refer to PDF] by deleting every edge [figure omitted; refer to PDF] of [figure omitted; refer to PDF] and replacing it by a vertex [figure omitted; refer to PDF] of degree 2 that is joined to [figure omitted; refer to PDF] and [figure omitted; refer to PDF] (see page 151 of [23]). The line graph of a graph [figure omitted; refer to PDF] , denoted by [figure omitted; refer to PDF] , is the graph whose vertices correspond to the edges of [figure omitted; refer to PDF] with two vertices of [figure omitted; refer to PDF] being adjacent if and only if the corresponding edges in [figure omitted; refer to PDF] share a common vertex [22].

It is amazing and interesting that [figure omitted; refer to PDF] , constructed from [figure omitted; refer to PDF] as the graph operation above, is equivalent to the line graph of the subdivision graph [figure omitted; refer to PDF] [22]; that is, [figure omitted; refer to PDF] .

Remark 4.

Note that there is an elementary and important property: if [figure omitted; refer to PDF] is an [figure omitted; refer to PDF] -regular graph (combinatorial network), then [figure omitted; refer to PDF] is also an [figure omitted; refer to PDF] -regular graph (combinatorial network); however, the topological structure of [figure omitted; refer to PDF] is quite more complicated than [figure omitted; refer to PDF] ; consequently, dealing with the problems of calculating Kirchhoff index of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] is not easy, even though we have handled the formulas for calculating the Kirchhoff index of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] in [24, 25].

Yin and Wang [26] have proved the following Lemma.

Lemma 5 (see [26]).

For [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] , the spectrum of Laplacian matrix of [figure omitted; refer to PDF] is [figure omitted; refer to PDF] where [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , are the eigenvalues of the Laplacian matrix of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the multiplicities of the eigenvalues [figure omitted; refer to PDF] .

M. Chen and B. X. Chen have studied the Laplacian spectra of [figure omitted; refer to PDF] in [3].

Lemma 6 (see [3]).

For [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] , the spectra of Laplacian matrix of [figure omitted; refer to PDF] are as follows:

(1) If [figure omitted; refer to PDF] , then [figure omitted; refer to PDF]

(2) If [figure omitted; refer to PDF] , then [figure omitted; refer to PDF]

where [figure omitted; refer to PDF] are the binomial coefficients and the elements in the first and second rows are the Laplacian eigenvalues of [figure omitted; refer to PDF] and the multiplicities of the corresponding eigenvalues, respectively.

Lemma 7 (see [11, 27]).

Let [figure omitted; refer to PDF] be a connected graph, with [figure omitted; refer to PDF] vertices, and [figure omitted; refer to PDF] are the Laplacian eigenvalues of [figure omitted; refer to PDF] ; then [figure omitted; refer to PDF]

Let [figure omitted; refer to PDF] be the characteristic polynomial of the Laplacian matrix of a graph [figure omitted; refer to PDF] ; the following results were shown in [28].

Lemma 8 (see [28]).

Let [figure omitted; refer to PDF] be an r-regular connected graph with [figure omitted; refer to PDF] vertices and [figure omitted; refer to PDF] edges; then [figure omitted; refer to PDF] where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the characteristic polynomials for the Laplacian matrix of graphs [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively.

Let [figure omitted; refer to PDF] be a bipartite graph with a bipartition; [figure omitted; refer to PDF] is called an [figure omitted; refer to PDF] -semiregular graph if all vertices in [figure omitted; refer to PDF] have degree [figure omitted; refer to PDF] and all vertices in [figure omitted; refer to PDF] have degree [figure omitted; refer to PDF] .

Lemma 9 (see [29]).

Let [figure omitted; refer to PDF] be an [figure omitted; refer to PDF] -semiregular connected graph with [figure omitted; refer to PDF] vertices and [figure omitted; refer to PDF] edges, and [figure omitted; refer to PDF] is the Laplacian characteristic polynomial of the line graph [figure omitted; refer to PDF] . Then [figure omitted; refer to PDF]

3. Main Results

Theorem 10.

For [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] , one has [figure omitted; refer to PDF]

Proof.

Notice that [figure omitted; refer to PDF] is [figure omitted; refer to PDF] -regular graph with [figure omitted; refer to PDF] vertices and [figure omitted; refer to PDF] edges. Suppose that [figure omitted; refer to PDF] has [figure omitted; refer to PDF] vertices and [figure omitted; refer to PDF] edges, for convenience, and denote the degree of vertices in [figure omitted; refer to PDF] by [figure omitted; refer to PDF] . Obviously, [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively.

From Lemma 9, we can get [figure omitted; refer to PDF]

By virtue of Lemma 8, it follows that [figure omitted; refer to PDF]

Replacing [figure omitted; refer to PDF] with [figure omitted; refer to PDF] in (9), we have [figure omitted; refer to PDF]

Substituting (8) with (10), the Laplacian characteristic polynomial of [figure omitted; refer to PDF] is [figure omitted; refer to PDF]

From the definition graph [figure omitted; refer to PDF] and (11), one can immediately obtain [figure omitted; refer to PDF]

Combining (12), [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , it holds that [figure omitted; refer to PDF] Since the roots of [figure omitted; refer to PDF] are [figure omitted; refer to PDF] where [figure omitted; refer to PDF] are the Laplacian eigenvalues of [figure omitted; refer to PDF] .

It follows from (12) that the Laplacian spectrum of [figure omitted; refer to PDF] is [figure omitted; refer to PDF] Noticing that [figure omitted; refer to PDF] has [figure omitted; refer to PDF] vertices, we get the following result from Lemmas 5 and 7 and (15). Therefore, [figure omitted; refer to PDF]

This completes the proof.

The following theorem [24] provided the closed-form formula expressing the Kirchhoff index of [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] .

Theorem 11 (see [24]).

Let [figure omitted; refer to PDF] be the binomial coefficients for [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] . Then [figure omitted; refer to PDF]

Theorem 12.

Let [figure omitted; refer to PDF] be the binomial coefficients for [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] . Then [figure omitted; refer to PDF]

Proof.

From Theorems 10 and 11 one can immediately arrive at the explicit formula expressing the Kirchhoff index of [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] .

Remark 13.

Theorem 11 gives the value of [figure omitted; refer to PDF] in a nice closed-form formula. In [30] a similar, slightly more involved, closed-form formula was given, and, moreover, an asymptotic value of [figure omitted; refer to PDF] was given for [figure omitted; refer to PDF] . Comparing the asymptotic relative sizes of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] in the present article, the latter is much larger than the former.

In the following, we will further address the Kirchhoff index of [figure omitted; refer to PDF] . Primarily, notice that [figure omitted; refer to PDF] is a regular graph with degree for any vertex and the Laplacian spectrum of [figure omitted; refer to PDF] is as follows:

(1) If [figure omitted; refer to PDF] , then [figure omitted; refer to PDF]

(2) If [figure omitted; refer to PDF] , then [figure omitted; refer to PDF]

In an almost identical way as Theorem 10, we derive the following formula expressing the Kirchhoff index of [figure omitted; refer to PDF] . The proof is omitted here for the completely similar deduction to Theorem 10.

Theorem 14.

For [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] , one has [figure omitted; refer to PDF]

In [25], the authors have proposed the following Kirchhoff index of [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] .

Theorem 15 (see [25]).

Let [figure omitted; refer to PDF] denote the binomial coefficients for [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] . Then

(1) [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , if [figure omitted; refer to PDF] ,

(2) [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , if [figure omitted; refer to PDF] .

Theorem 16.

Let [figure omitted; refer to PDF] denote the binomial coefficients for [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] . Then

(1) [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , if [figure omitted; refer to PDF] ,

(2) [figure omitted; refer to PDF] + [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , if [figure omitted; refer to PDF] .

Proof.

From Theorems 14 and 15, it is not difficult to deduce the above formula expressing the Kirchhoff index of [figure omitted; refer to PDF] with any integer [figure omitted; refer to PDF] .

Remark 17.

Theorems 12 and 16 have presented a method to calculate the Kirchhoff index of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , which is difficult to calculate directly. We found a relationship between the graph [figure omitted; refer to PDF] and [figure omitted; refer to PDF] by deducing the characteristic polynomial of the Laplacian matrix and obtained the Laplacian spectrum of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . If we can compute the Kirchhoff index [figure omitted; refer to PDF] readily, then, by Laplacian spectrum of [figure omitted; refer to PDF] , we can also obtain the Kirchhoff index [figure omitted; refer to PDF] which is hard to calculate immediately. Furthermore, utilizing this approach one can also formulate the Kirchhoff index of other general graphs.

4. Some Examples

To demonstrate the theoretical analysis, we provide some examples in this subsection, which are an application of our results. Without loss of generality, we suppose that the case is [figure omitted; refer to PDF] for simplicity. Obviously, [figure omitted; refer to PDF] , and the eigenvalues of the Laplacian matrix of [figure omitted; refer to PDF] are [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Based on Lemma 7, it is easy to obtain that [figure omitted; refer to PDF] According to the consequence of Theorem 10, one can readily derive that [figure omitted; refer to PDF] On the other hand, we use another approach to calculate [figure omitted; refer to PDF] . For a circulant graph [figure omitted; refer to PDF] , the authors of [31] showed that [figure omitted; refer to PDF] The first equality holds if and only if [figure omitted; refer to PDF] is [figure omitted; refer to PDF] and the second does if and only if [figure omitted; refer to PDF] is [figure omitted; refer to PDF] .

By virtue of the definition of [figure omitted; refer to PDF] , it is not difficult to get that [figure omitted; refer to PDF] .

Consequently, the same Kirchhooff index can be drawn as follows: [figure omitted; refer to PDF]

As the application of Theorem 14, we proceed to derive that [figure omitted; refer to PDF] .

Note that the eigenvalues of the Laplacian matrix of [figure omitted; refer to PDF] are [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Based on Lemma 7, we have [figure omitted; refer to PDF] Similarly, according to the consequence of Theorem 14, it holds that [figure omitted; refer to PDF]

Summing up the examples, the results above coincide the fact, which show our theorems are correct and effective.

Acknowledgments

The work of J. B. Liu was supported by Anhui Provincial Natural Science Foundation under Grant no. KJ2013B105 and the National Science Foundation of China under Grant nos. 11471016 and 11401004. The work of F. T. Hu was supported by Anhui Provincial Natural Science Foundation (1408085QA03) and the National Science Foundation of China under Grant no. 11401004. The authors would like to express their sincere gratitude to the anonymous referees for their valuable suggestions, which led to a significant improvement of the original paper.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] M. Xu, X. D. Hu, J. M. Xu, "Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes," Applied Mathematics and Computation , vol. 189, no. 2, pp. 1393-1401, 2007.

[2] A. El-Amawy, S. Latifi, "Properties and performance of folded hypercubes," IEEE Transactions on Parallel and Distributed Systems , vol. 2, no. 1, pp. 31-42, 1991.

[3] M. Chen, B. X. Chen, "Spectra of folded hypercubes," Journal of East China Normal University , vol. 2, no. 39, pp. 39-46, 2011.

[4] S. Cao, H. Liu, X. He, "On constraint fault-free cycles in folded hypercube," International Journal of Applied Mathematics and Statistics , vol. 42, no. 12, pp. 38-44, 2013.

[5] J.-B. Liu, X.-F. Pan, J. Cao, "Some properties on Estrada index of folded hypercubes networks," Abstract and Applied Analysis , vol. 2014, 2014.

[6] W. Qiu, W. Yan, "The coefficients of Laplacian characteristic polynomials of graphs," Linear Algebra and Its Applications , vol. 436, no. 7, pp. 2474-2479, 2012.

[7] J. M. Xu Topological Strucure and Analysis of Interconnction Networks , Kluwer Academic Publishers, Dordrecht, The Netherlands, 2001.

[8] D. J. Klein, M. Randic, "Resistance distance," Journal of Mathematical Chemistry , vol. 12, no. 1-4, pp. 81-95, 1993.

[9] L. Ye, "On the Kirchhoff index of some toroidal lattices," Linear and Multilinear Algebra , vol. 59, no. 6, pp. 645-650, 2011.

[10] B. Zhou, N. Trinajstic, "A note on Kirchhoff index," Chemical Physics Letters , vol. 455, no. 1-3, pp. 120-123, 2008.

[11] H.-Y. Zhu, D. J. Klein, I. Lukovits, "Extensions of the Wiener number," Journal of Chemical Information and Computer Sciences , vol. 36, no. 3, pp. 420-428, 1996.

[12] Z. You, L. You, W. Hong, "Comment on Kirchhoff index in line, subdivision and total graphs of a regular graph," Discrete Applied Mathematics , vol. 161, no. 18, pp. 3100-3103, 2013.

[13] W. J. Xiao, I. Gutman, "Resistance distance and Laplacian spectrum," Theoretical Chemistry Accounts , vol. 110, no. 4, pp. 284-289, 2003.

[14] E. Estrada, N. Hatano, "Topological atomic displacements, Kirchhoff and Wiener indices of molecules," Chemical Physics Letters , vol. 486, no. 4-6, pp. 166-170, 2010.

[15] A. D. Maden, A. S. Cevik, I. N. Cangul, K. C. Das, "On the KIRchhoff matrix, a new KIRchhoff index and the KIRchhoff energy," Journal of Inequalities and Applications , vol. 2013, article 337, pp. 83-94, 2013.

[16] J. B. Liu, X. F. Pan, J. Cao, F. F. Hu, "A note on 'some physical and chemical indices of clique-inserted lattices'," Journal of Statistical Mechanics: Theory and Experiment , vol. 10, no. 6, pp. 1-8, 2014.

[17] J.-B. Liu, X.-F. Pan, F.-T. Hu, F.-F. Hu, "Asymptotic Laplacian-energy-like invariant of lattices," Applied Mathematics and Computation , vol. 253, pp. 205-214, 2015.

[18] J.-B. Liu, X.-F. Pan, "Asymptotic incidence energy of lattices," Physica A. Statistical Mechanics and its Applications , vol. 422, pp. 193-202, 2015.

[19] C. Arauz, "The Kirchhoff indexes of some composite networks," Discrete Applied Mathematics , vol. 160, no. 10-11, pp. 1429-1440, 2012.

[20] M. Bianchi, A. Cornaro, J. L. Palacios, A. Torriero, "Bounds for the Kirchhoff index via majorization techniques," Journal of Mathematical Chemistry , vol. 51, no. 2, pp. 569-587, 2013.

[21] R. Indhumathi, S. A. Choudum, "Embedding certain height-balanced trees and complete p^m -ary trees into hypercubes," Journal of Discrete Algorithms , vol. 22, pp. 53-65, 2013.

[22] D. J. Klein, E. Yi, "A comparison on metric dimension of graphs, line graphs, and line graphs of the subdivision graphs," European Journal of Pure and Applied Mathematics , vol. 5, no. 3, pp. 302-316, 2012.

[23] G. Chartrand, P. Zhang Introduction to Graph Theory , McGraw-Hill, Kalamazoo, Mich, USA, 2004.

[24] J. Liu, J. Cao, X.-F. Pan, A. Elaiw, "The Kirchhoff index of hypercubes and related complex networks," Discrete Dynamics in Nature and Society , vol. 2013, 2013.

[25] J. Liu, X.-F. Pan, Y. Wang, J. Cao, "The Kirchhoff index of folded hypercubes and some variant networks," Mathematical Problems in Engineering , vol. 2014, 2014.

[26] J. H. Yin, R. G. Wang, "Spectra of Laplacian matrices of hypercubes," Journal of Zhejiang University. Science Edition , vol. 34, no. 3, pp. 321-323, 2007.

[27] I. Gutman, B. Mohar, "The quasi-Wiener and the Kirchhoff indices coincide," Journal of Chemical Information and Computer Sciences , vol. 36, no. 5, pp. 982-985, 1996.

[28] X. Gao, Y. Luo, W. Liu, "Kirchhoff index in line, subdivision and total graphs of a regular graph," Discrete Applied Mathematics , vol. 160, no. 4-5, pp. 560-565, 2012.

[29] B. Mohar, Y. Alavi, "The Laplacian spectrum of graphs," Graph Theory, Combinatorics, and Applications , vol. 2, pp. 871-898, Wiley-Interscience, 1991.

[30] J. L. Palacios, J. M. Renom, "Bounds for the Kirchhoff index of regular graphs via the spectra of their random walks," International Journal of Quantum Chemistry , vol. 110, no. 9, pp. 1637-1641, 2010.

[31] H. P. Zhang, Y. J. Yang, "Resistance distance and kirchhoff index in circulant graphs," International Journal of Quantum Chemistry , vol. 107, no. 2, pp. 330-339, 2007.