# Upper and Lower Bounds for the Kirchhoff Index of then-Dimensional Hypercube Network

Authors: Jia-Bao Liu; Jing Zhao; Zhi-Yu Shi; Jinde Cao; Fuad E. Alsaadi
Journal: Complexity
 (2020)

---

## Abstract

The hypercubeQn is one of the most admirable and efficient interconnection network due to its excellent performance for some practical applications. The Kirchhoff index KfG is equal to the sum of resistance distances between any pairs of vertices in networks. In this paper, we deduce some bounds with respect to Kirchhoff index of hypercube network Qn.


---

## Body

## 1. Introduction

Network is usually modelled by a connected graphG=VG,EG with order n, labeled as VG=v1,v2,…,vn and EG=e1,e2,…,em. The adjacency matrix AG of G is a square matrix with n vertices, in which elements aij are 1 or 0, depending on whether there is an edge or not between vertices i and j. The degree diagonal matrix of G is denoted by DG=diagd1,d2,…,dn, where d1,d2,…,dn are the degree of vertices v1,v2,…,vn, respectively. Together with the adjacency and degree matrix, one arrives at the Laplacian matrix, whose expression can be written as LG=DG−AG. For other notations and graph theoretical terminologies that not state here, we follow [1].Various parameters are always used to characterize and describe the complex networks of which the fundamental one is named as the distancedij, concerned as the shortest path between the vertices i and j in networks. Similarly considering the distance dij, Klein and Randić in 1993 presented a novel distance function, named as resistance distance [2]. Denote rij the resistance distance between two arbitrary vertices i and j in electrical networks by replacing every edge by a unit resistor [3–7]. The Kirchhoff index KfG of networks is defined as(1)KfG=∑i<jrijG.The Kirchhoff index has attracted more and more attentions due to its practical applications in the fields of physical interpretations, electric circuit, and so on [8–11]. The Kirchhoff index of some product graphs, join graphs, and corona graphs were studied [5, 7]. The more results of the applications on the Kirchhoff index were explored in [12–14].In what follows, the rest of the context is summarized. Section2 proposes the main definition and preliminaries in our discussion. Some bounds on the Kirchhoff index of hypercubes Qn are deduced in Section 3. We conclude the paper in Section 4.


## 2. Definition and Preliminaries

In this section, we recall some basic definition in graph theory. The hypercube networkQn 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 hypercube network Qn admits several definitions of which one is stated as below [15].The hypercube networkQn is repeatedly constructed by making two copies of Qn−1, written as Qn−10 and Qn−11, respectively. Meanwhile, adding repeatedly 2n−1 edges as below, let VQn−10=0U=0u2u3…un:ui=0or1 and VQn−11=1V=1v2v3…vn:vi=0or1. A node 0U=0u2u3…un of Qn−10 is linked to another node 1V=1v2v3…vn of Qn−11 if and only if ui=vi for each i,2≤i≤n.The hypercube networkQn obtained more and more admirable concentrations due to its surprising properties, for instance, symmetry, regular structure, strong connectivity, small diameter, and so on [16, 17]. For more results on the hypercube network and its applications, see [18–21].Next, we recall the formula for the Kirchhoff index in the hypercubeQn with n≥2.Theorem 1 (see [3]).
For the hypercube networkQn with n≥2, (2)KfQn=2n∑i=1nni12i,where 2ii=1,…,n is the eigenvalue of the Laplacian matrix of the hypercube network and the binomial coefficients niare the multiplicities of the eigenvalues 2i.Theorem 2 (see [22]).
(3)limn⟶∞∑i=0n−1n2in−i=2.The authors of [23] obtained a closed-form formula for the Kirchhoff index of the d-dimensional hypercube and found the asymptotic value 22d/d by using probabilistic tools. The result of Theorem 3 is obtained by directly calculating the eigenvalues of the Laplacian matrix of the hypercube network, which is different from the technique in [23].


## 3. Main Results

In this section, one will estimate the Kirchhoff index ofn-dimensional hypercube, i.e., our goal is to estimate the quantity:(4)2n∑i=1nni12i.Theorem 3.
For the hypercube networkQn with n≥2, then(5)4nnnn+1−nn+22n+1n+1≤KfQn.
Consider that(6)∑i=1nni1i≥∑i=1nni1i+1=n112+n213+…+nn1n+1=12n!1!n−1!+13n!2!n−2!+…+1n+1=1n+1n+1!2!n−1!+1n+1n+1!3!n−2!+…+1n+1=∑i=1nn+1i+11n+1.By virtue of(7)∑i=1nn+1i+1=2n+1−n−2.By means of calculating the right of equation (6), one can establish the following identity:(8)∑i=1nn+1i+11n+1=2n+1−n−2n+1.Since(9)2n+1−n−2n+1≤∑i=1nni1i=2∑i=1nni12i,2n+1−n−2n+1≤2∑i=1nni12i.Hence,(10)2n2nn+1−2n−1n+2n+1=2n−12n+1−n−2n+1≤KfQn=2n∑i=1nni12i.Simply, from the left of the above inequality, we obtain(11)4nnnn+1−nn+22n+1n+1≤KfQn.Apparently, the left of the above inequality converges to the asymptotic value22d/d for large enough n. The proof of lower bound is completed.For the upper bound, we have similar theorem to consider as follows.Theorem 4.
For the hypercube networksQn with n≥2, then(12)KfQn≤4nn2nn+1−n+22nn+1,(13)∑i=1n12iCni≤∑i=1n1i+1Cni=12Cn1+13Cn2+…+1n+1Cnn=12n!1!n−1!+13n!2!n−2!+…+1n+1=1n+1n+1!2!n−1!+1n+1n+1!3!n−2!+…+1n+1=∑i=1n1n+1Cn+1i+1.Based on equation (8), we can obtain that(14)2n∑i=1nCni2i=KfQn≤2n2n+1−n−2n+1.Hence,(15)KfQn≤2n2n+1−n−2n+1=4nn2nn+1−n+22nn+1.The above estimate looks a little complicated. The upper bound is roughly twice the asymptotic value. Hence, a new upper bound is explored as follows.Theorem 5.
For the hypercube networkQn with n≥2, (16)KfQn≤4nn.Following the identity which is obtained in [24],(17)∑i=1nxii=1n+1n−1+⋯+1+∑i=1nnix−1ii.Fixingx=2, one arrives at(18)∑i=1nni1i=∑i=1n2ii−1n+1n−1+⋯+1.Namely,(19)∑i=1nni1i=∑i=1n2i−1i.According to equation (19) and Theorem 2, one obtains(20)KfQn=2n−1⋅∑i=1n2i−1i.Using equation (20), one has(21)KfQn≤2n−1⋅∑i=1n2ii.On the contrary,(22)2n−1⋅∑i=1n2ii=1n⋅22n−1⋅∑i=0n−1n2in−i.Using Theorem2 and substituting equations (22) to (21), one obtains the desired result:(23)KfQn≤4nn.This has completed the proof.


## 4. Further Discussion

We, at this place, try another way to estimate the Kirchhoff index ofn-dimensional hypercubes.Theorem 6.
For the hypercube networksQn with n≥2, then(24)KfQn=2n−1∑i=1n2i−1i.LetSn=∑i=1nCni/i, then(25)Sn−Sn−1=∑i=1nCnii−∑i=1n−1Cn−1ii=1n+∑i=1n−1Cnii−∑i=1n−1Cn−1ii=1n+∑i=1n−11iCni−Cn−1i=1n+∑i=1n−11iCn−1i−1.Consequently,(26)n⋅Sn−Sn−1=1+∑i=1n−1n!i!n−i!=1+∑i=1n−1Cni=2n−1.One can easily check thatS1=1. Hence, Sn−Sn−1=2n/n−1/n.By virtue of the above equality, we obtain(27)Sn=∑i=1n2ii−∑i=1n1i.Therefore,(28)KfQn=2n−1∑i=1n2i−1i.The proof of Theorem6 is completed.



---

*Source: 5307670-2020-06-16.xml*