# Computing Eccentricity-Based Topological Indices of 2-Power Interconnection Networks

Authors: Muhammad Imran; Muhammad Azhar Iqbal; Yun Liu; Abdul Qudair Baig; Waqas Khalid; Muhammad Asad Zaighum
Journal: Journal of Chemistry
 (2020)

---

## Abstract

In a connected graphG with a vertex v, the eccentricity εv of v is the distance between v and a vertex farthest from v in the graph G. Among eccentricity-based topological indices, the eccentric connectivity index, the total eccentricity index, and the Zagreb index are of vital importance. The eccentric connectivity index of G is defined by ξG = ∑v∈VGdvεv, where dv is the degree of the vertex v and εv is the eccentricity of v in G. The topological structure of an interconnected network can be modeled by using graph explanation as a tool. This fact has been universally accepted and used by computer scientists and engineers. More than that, practically, it has been shown that graph theory is a very powerful tool for designing and analyzing the topological structure of interconnection networks. The topological properties of the interconnection network have been computed by Hayat and Imran (2014), Haynes et al. (2002), and Imran et al. (2015). In this paper, we compute the close results for eccentricity-based topological indices such as the eccentric connectivity index, the total eccentricity index, and the first, second, and third Zagreb eccentricity index of a hypertree, sibling tree, and X-tree for k-level by using the edge partition method.


---

## Body

## 1. Introduction

The advancement of large-scale integrated circuit technology has enabled the construction of complex interconnection networks. Graph theory provides a fundamental tool for designing and analyzing such networks. Graph theory and interconnection networks provide a thorough understanding of these interrelated topics [1–3] The architecture of an interconnected network is represented by a graph, where nodes represent the processors and edges represent the links between processors. Electric power companies need to continually monitor the state of their systems as in the case of the voltage magnitude at loads and the machine phase angle at generators. In the electric power system, a vertex represents an electric node and an edge represents a transmission line joining two electrical nodes [4, 5]. Chemical graph theory is a branch of mathematical chemistry in which we apply tools of graph theory to model the chemical phenomenon mathematically. This theory contributes a prominent role in the fields of chemical sciences. A molecular or chemical graph is a simple finite graph in which vertices denote the atoms and edges denote the chemical bonds in the underlying chemical structure. A topological index is actually a numeric quantity associated with chemical constitution purporting for correlation of the chemical structure with many physiochemical properties, chemical reactivity, and biological activities. Let G be a graph with u and v being the vertices of G, then the distance du,v is defined as the shortest length between u and v. The eccentricityεv of a vertex v∈VG is defined as(1)εv=maxdv,w|w∈VG.The minimum eccentricity in a graphG is known as the radiusGradG, while the maximum eccentricity in a graph G is known as the diameter2p−2. Topological descriptors play an important role in the quantitative structure-activity (QSAR) and structure-property (QSPR) study. Topological indices, which are based on eccentricity of the vertices in a graph G, are known as eccentricity-based topological indices. The eccentric connectivity index [6] of G is defined by(2)ξG=∑vϵVGdvεu,where dv is the degree of the vertex v and εv is the eccentricity of v in G.Thetotal eccentricity index [7] is defined as the summation of eccentricity of each vertex in graph G. In other words, when the vertex degrees are not considered in the eccentric connectivity index, then we obtain the total eccentricity index:(3)ζG=∑uϵVGεu,where εv is the eccentricity of u in G.Zagreb indices [8] have been introduced more than thirty years ago. Let G be a graph with u and v being the vertices of G; then the Zagreb indices are defined as follows:(4)M1G=∑v∈VGdv2,M2G=∑uv∈EGdudv.Some new modified versions of Zagreb indices [9] are expressed in terms of eccentricity as follows:(5)M1⋆G=∑uv∈EGεu+εv,M1⋆⋆G=∑v∈VGεv2,M2⋆G=∑uv∈EGεuεv.On further results for certain degree-based topological indices of networks and nanostructures, consult [1, 10–13]. A tree is a connected acyclic graph, and the common type of a tree is a binary tree. A binary tree is made of nodes, where each node contains a left reference, a right reference, and a data element. The top most node is called the root. The vertex of the binary tree has three fields. The first field represents data, while the second and third contain information of the left and right sons of the vertex. If each internal vertex/node has exactly two descendents, then the binary tree is said to be a complete binary tree as shown in Figure 1. The basic skeleton of the hypertreek-level is a complete binary tree HTk. The nodes of the trees are labeled in such a way that root node has label 1. The root is at level 0. Labels of the left and right children are formed by appending 0 and 1, respectively, to the labels of the parent node. Here, the children of the nodes x are labeled as 2x and 2x+1. Additional links in a hypertree are horizontal, and two nodes in the same level of the tree are joined if their label difference is 2i−2 [14]. The hypertree k-level HTk shown in Figure 2 has vertices 2k+1−1 and edges 32k−1.Figure 1
Binary tree.Figure 2
k-level hypertree HTk.


## 2. Main Results

In this section, we compute the close results for eccentricity-based topological indices such as the eccentric connectivity index, the total eccentricity index, and the first, second, and third Zagreb eccentricity index of a hypertree, sibling tree, andX-tree for k-level by using the edge partition method. The molecular topological descriptors of fullerenes and several interconnection networks have been already computed in the literature [1–3, 15].In the next theorem, an exact expression for the eccentric connectivity index for a binary tree is computed.Theorem 1.
Consider the graphG≅HTk, then the eccentric connectivity index is equal to(6)ξG=2k+4∑i=1k−1∑p=k2k−22ip+2k+12k−1.Proof.
In order to prove the above result, we use the formula of the eccentric connectivity index:(7)ξG=∑v∈VGdvεv.
By using Table1, we have(8)ξG=2∑p=k∑i=02ip+4∑i=1k−1∑p=k2k−22ip+2∑i=k∑p=k2p−12i.
After an easy calculation, we get(9)ξG=2k+4∑i=1k−1∑p=k2k−22ip+2k+12k−1.
The total eccentricity index of a binary tree is computed in the following theorem.Table 1
Vertices partition of a hypertree (k-level) based on degree and eccentricity of each vertex with the existence of its frequencies.
dvεvFrequencyRange ofiRange ofp2p2ii=0p=k4p2i1≤i≤k−1k≤p≤2k−222p−12ii=kp=kTheorem 2.
Consider the graphG≅HTk, then the total eccentricity index is equal to(10)ζG=k+∑i=1k−1∑p=k2k−22ip+2k−12k.Proof.
LetG be a graph of a hypertree (k-level). To prove (10), we use the total eccentricity index formula:(11)ζG=∑uεVGεu.
By using Table1, we get(12)ζG=∑p=k∑i=02ip+∑i=1k−1∑p=k2k−2p×2i+∑i=k∑p=k2i2p−1.
After an easy calculation, we get(13)ζG=k+∑i=1k−1∑p=k2k−22ip+2k−12k.
The first Zagreb eccentricity index of a binary tree is computed in the following theorem.Theorem 3.
Consider the graphG≅HTk, then the first Zagreb eccentricity index is equal to(14)M1⋆G=6k+∑i=1k−1∑p=k2k−22p+12i+1+∑i=1k−1∑p=k2k−22p+22i.Proof.
In order to proof (14), we use the first Zagreb eccentricity index formula:(15)M1⋆G=∑uvϵEGεu+εv.
By using Table2, we get(16)M1⋆G=3∑p=k∑i=02p2i+∑i=1k−1∑p=k2k−22p+12i+1+∑i=1k−1∑p=k2k−22p+22i.
After an easy calculation, we get(17)M1⋆G=6k+∑i=1k−1∑p=k2k−22p+12i+1+∑i=1k−1∑p=k2k−22p+22i.Table 2
Edge partition of a hypertree (k-level) based on eccentricity of end vertices of each edge with existence of its frequencies.
εu,εvFrequencyRange ofiRange ofpp,p3.2ii=0p=kp,p+12i+11≤i≤k−1k≤p≤2k−2p+1,p+12i1≤i≤k−1k≤p≤2k−2Theorem 4.
Consider the graphG≅HTk, then the second Zagreb eccentricity index is equal to(18)M1⋆⋆G=k2+∑i=1k−1∑p=k2k−2p22i+2k−122k.Proof.
LetG be a graph of a hypertree (k-level). The formula of the second Zagreb eccentricity index is given by(19)M1⋆⋆G=∑vϵVGεv2.
By using Table1, we get(20)M1⋆⋆G=∑p=k∑i=0p22i+∑i=1k−1∑p=k2k−2p22i+∑i=k∑p=k2p−122i.
After an easy calculation, we get(21)M1⋆⋆G=k2+∑i=1k−1∑p=k2k−2p22i+2k−122k.Theorem 5.
Consider the graphG≅HTk, then the third Zagreb eccentricity index is equal to(22)M2⋆G=3k2+∑i=1k−1∑p=k2k−2pp+12i+1+∑i=k∑p=kp+122i.Proof.
In order to prove (22), we use the formula of the third Zagreb eccentricity index:(23)M2⋆G=∑uvϵEGεu×εv.
By using Table2, we get(24)M2⋆G=3∑p=k∑i=0p22i+∑i=1k−1∑p=k2k−2pp+12i+1+∑i=k∑p=kp+122i.
After an easy calculation, we get(25)M2⋆G=3k2+∑i=1k−1∑p=k2k−2pp+12i+1+∑i=1k−1∑p=k2k−2p+122i.
The 1-rootedsibling treeSTk1 shown in Figure 3 is obtained from the 1-rooted complete binary tree Tk1 by adding edges (sibling edges) between the left and right children of the same parent node [16].
AnX-treeXTk shown in Figure 4 is obtained from a complete binary tree on 2k+1−1 vertices of height 2i−1 and adding paths Pi left to right through all the vertices at level i, 1≤i≤k.
A graphG1=V1,E1 is said to be isomorphic to the graph G2=V2,E2, if there is a one-to-one correspondence between the vertex sets V1 and V2 and a one-to-one correspondence between the edge sets E1 and E2 in such a way that if e1 is an edge with end vertices u1 and v1 in G1, then the corresponding edge e2 in G2 has its end points in the vertices u2 and v2 in G2 which correspond to u1 and v1, respectively. Such a pair of correspondences is called the graph isomorphism.Figure 3
1-rooted sibling treeSTk1.Figure 4
k-level X-tree XTk.Remark 1.
HTk≇STk1, but their topological eccentricity-based indices are equal:(26)ξHTk=ξSTk1,ζHTk=ζSTk1,M1⋆HTk=M1⋆STk1,M1⋆⋆HTk=M1⋆⋆STk1,M2⋆HTk=M2⋆STk1.Theorem 6.
Consider the graphG≅XTk and k≥3, then the eccentric connectivity index is equal to(27)ξG=2k+8∑p=k2k−2p+42k−1+5∑p=k2k−3∑i=1k−22ip+32k−22k−15∑p=k+2,k>32k−2∑i=1,k>3k−322i−1p+32k−122k−2−1.Proof.
In order to prove the above result, we use the formula of the eccentric connectivity index:(28)ξG=∑v∈VGdvεv.
By using Table3, we have(29)ξG=2∑p=k,k≥3p∑i=02i+4∑i=12i∑p=k,k≥32k−2p+2∑i=12i∑p=k,k≥32p−1+5∑p=k,k≥32k−3p∑i=1,k≥3k−22i+5∑p=k+2,k>32k−2p∑i=1,k>3k−322i−1+3∑p=k,k≥32p−2∑i=k−1,k≥32i.
After an easy calculation, we get(30)ξG=2k+8∑p=k2k−2p+4∑p=k2p−1+5∑p=k2k−3∑i=1k−22ip+32k−22k−15∑p=k+2,k>32k−2∑i=1,k>3k−322i−1p+32k−122k−2−1.Table 3
Vertices partition of anX-tree (k-level) based on degree and eccentricity of each vertex with the existence of its frequencies.
dvεvFrequencyRange ofiRange ofp2p2ii=0p=k4p2ii=1k≤p≤2k−222p−12ii=1p=k5p2i1≥i≥k−2k≥p≥2k−35p22i−11≥i≥k−3, k>3k+2≥p≥2k−2, k>332p−122i−1i=k−2p=k32p−22ii=k−1p=kTheorem 7.
Consider the graphG≅XTk and k≥3, then the total eccentricity index is equal to(31)ζG=k+2∑p=k2k−2p+22k−1+∑p=k2k−3∑i=1k−22ip+∑p=k+2,k>32k−2∑i=1,k>3k−322i−1p+2k−122k−2−1+2k−22k−1.Proof.
LetG be a graph of an X-tree (k-level). In order to prove, we use the total eccentricity index formula:(32)ζG=∑uϵVGεu.
By using Table3, we get(33)ζG=∑p=kp∑i=02i+∑i=12i∑p=k2k−2p+∑i=12i∑p=k2p−1+∑p=k2k−3p∑i=1k−22i+∑p=k+2,k>32k−2p∑i=1,k>3k−322i−1+∑p=k2p−1∑i=k−222i−1+∑p=k2p−2∑i=k−12i.
After an easy calculation, we get(34)ζG=k+2∑p=k2k−2p+22k−1+∑p=k2k−3∑i=1k−22ip+∑p=k+2,k>32k−2∑i=1,k>3k−322i−1p+2k−122k−2−1+2k−22k−1.Theorem 8.
Consider the graphG≅XTk and k≥3, then the first Zagreb eccentricity index is equal to(35)M1⋆G=12k+∑i=1k−2∑p=k+12k−22p32i−1+4k−32k−1+2+∑i=1k−2∑p=k2k−32p+1232i−1+1+4k−222k−2−1.Proof.
In order to prove the above result, we use the first Zagreb eccentricity index formula:(36)M1⋆G=∑uvϵEGεu+εv.
By using Table4, we get(37)M1⋆G=∑p=kp+p∑i=062i+∑i=1k−232i−1∑p=k+12k−2p+p+∑i=1k−2232i−1+1∑p=k2k−3p+p+1+∑p=k2p−2+2p−1∑i=k−22i+1+2+∑p=k2p−1+2p−1∑i=k−222i−1.
After an easy calculation, we get(38)M1⋆G=12k+∑i=1k−2∑p=k+12k−22p32i−1+4k−32k−1+2+∑i=1k−2∑p=k2k−32p+1232i−1+1+4k−222k−2−1.Table 4
Edge partition of anX-tree (k-level) based on eccentricity of end vertices of each edge with existence of its frequencies.
εu,εvFrequencyRange ofiRange ofpp,p62ii=0p=kp,p32i−11≤i≤k−2k+1≤p≤2k−2p,p+1232i−1+11≤i≤k−2k≤p≤2k−32p−2,2p−12i+1+2i=k−2p=k2p−1,2p−122i−1i=k−2p=kTheorem 9.
Consider the graphG≅XTk and k≥3, then the second Zagreb eccentricity index is equal to(39)M1⋆⋆G=k2+2∑p=k2k−2p2+22k−12+∑p=k2k−3∑i=1k−22ip2+∑p=k+2,k>32k−2∑i=1k−322i−1p2+2k−1222k−2−1+2k−222k−1.Proof.
LetG be a graph of an X-tree (k-level) and k≥3. The formula of the second Zagreb eccentricity index is given by(40)M1⋆⋆G=∑vϵVGεv2.
By using Table3, we get the following expression:(41)M1⋆⋆G=∑p=kp2∑i=02i+∑i=12i∑p=k2k−2p2+∑i=12i∑p=k2p−12+∑i=1k−22i∑p=k2k−3p2+∑i=1,k>3k−322i−1∑p=k+2,k>32k−2p2+∑i=k−222i−1∑p=k2p−12+∑i=k−12i∑p=k2p−22.
After an easy calculation, we get(42)M1⋆⋆G=k2+2∑p=k2k−2p2+22k−12+∑p=k2k−3∑i=1k−22ip2+∑p=k+2,k>32k−2∑i=1k−322i−1p2+2k−1222k−2−1+2k−222k−1.Theorem 10.
Consider the graphG≅XTk and k≥3, then the third Zagreb eccentricity index is equal to(43)M2⋆G=6k2+∑p=k+12k−2∑i=1k−232i−1p2+∑p=k2k−3∑i=1k−2pp+1232i−1+1+2k−12k−22k−1+2+2k−1222k−2−1.Proof.
In order to prove the above result, we use the formula of the third Zagreb eccentricity index:(44)M2⋆G=∑uvϵEGεu×εv.
By using Table4, we get(45)M2⋆G=∑p=kp2∑i=062i+∑i=1k−232i−1∑p=k+12k−2p2+∑i=1k−2232i−1+1∑p=k2k−3pp+1+∑i=k−22i+1+2∑p=k2p−22p−1+∑i=k−222i−1∑p=k2p−12p−1.
After an easy calculation, we get(46)M2⋆G=6k2+∑p=k+12k−2∑i=1k−232i−1p2+∑p=k2k−3∑i=1k−2pp+1232i−1+1+2k−12k−22k−1+2+2k−1222k−2−1.


## 3. Conclusion

In this paper, we have computed the eccentricity-based topological indices such as the eccentric connectivity index, the total eccentricity index, and the first, second, and third Zagreb eccentricity index for certain interconnection networks such as a hypertree, sibling tree, andX-tree k-level. These results are useful in topological characterization of these important chemical networks.



---

*Source: 3794592-2020-06-13.xml*