# On Topological Indices for New Classes of Benes Network

Authors: Aftab Hussain; Muhammad Numan; Nafisa Naz; Saad Ihsan Butt; Adnan Aslam; Asfand Fahad
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Topological indices (TIs) transform a molecular graph into a number. The TIs are a vital tool for quantitative structure activity relationship (QSAR) and quantity structure property relationship (QSPR). In this paper, we constructed two classes of Benes network: horizontal cylindrical Benes networkHCBr and vertical cylindrical Benes network obtained by identification of vertices of first rows with last row and first column with last column of Benes network, respectively. We derive analytical close formulas for general Randić connectivity index, general Zagreb, first and the second Zagreb (and multiplicative Zagreb), general sum connectivity, atom-bond connectivity (VCBr), and geometric arithmetic ABC index of the two classes of Benes networks. Also, the fourth version of GA and the fifth version of ABC indices are computed for these classes of networks.


---

## Body

## 1. Introduction

The processing nodes in an interconnection network are the multiprocessor used to build a network of homogeneously same processor memory pairs. Programs are compiled and executed through message sending. Considerable importance to the architecture and utilization of multiprocessor interconnection network is due to low cost, more efficient microprocessors, and chips [1]. Interconnection networks resembled the communication pattern of the natural scenario, which make it more valuable and important. Most of the networks are interconnected and dependent on each other which need to be reviewed for the future work.Graphs are used to design interconnected networks in a very natural way, in which the processors or components represent vertices and edges represent the communication links, e.g., fiber optic cables. The way in which all these components work will be carried out by incidence functions. Graphs show the topological properties of the networks. Therefore, the graph and networks are basically the same in a sense; that is, when we are considering networks, components, and links, we actually speak of graphs, vertices, and edges.In Fourier transform networks, butterfly graphs are the basic graphs that can accomplish FFT very proficiently. There are series of interconnection patterns and switching stages in a butterfly network that permitsn inputs to be linked to n outputs. The Benes network consists of butterflies connected back to back. The Benes network is known for permutation routing [2]. They are significant multistage interconnection networks, which enjoy striking topologies for communication networks [3]. The use of Benes network is in parallel computing systems such as SP1/SP2, IBM, NEC Cenju-3, and MIT Transit Project. It is also used in the internal structures of optical couplers [4, 5]. There are 2r+1 levels in an r-dimensional Benes network where every level has 2r nodes. An r-dimensional butterfly is formed between the level 0 to level r nodes. The back to back butterflies share the middle level to form a Benes network. We denote an r-dimensional Benes by Br. Figure 1 shows the graph 3-dimensional Benes network B3.Figure 1
3-dimensional Benes network.From now onward, we denote byG a connected, simple graph with vertex and edge set by VG and EG. Moreover, for a∈VG, da, Na, and Sa present its degree, neighbors, and sum of degrees. For more details on undefined terminology, we refer the readers to [6–8].Several invariants assigned to graphs (or molecular structure) establish correlations between its structure and chemical/physical aspects. These graph invariants are named as topological indices. Several degree-dependent TIs have been formulated so far and are found to be useful in predicting the physical/chemical properties of an underlying molecular structure. For instance, there is a virtuous correlation among the Randic´ index (RI) and numerous physicochemical features of alkanes including chromatographic retention times, boiling points, and surface areas. The Zagreb indices (ZIs) and its different variants contribute to understand the complexity of (molecular) structures [9–13], chirality [14], ZE isomerism [15], and heterosystems [16], whilst the overall ZIs show a latent applicability to derive multilinear regression models. The ABC index offers a good model for the strain energy of cycloalkanes and stability of linear and branched alkanes [17, 18]. In this respect, computing different forms of TIs has provided the indicators of such medicinal conduct of numerous compounds and drugs. The mathematical forms of degree-based topological descriptors, which we discuss in this article, are depicted in Table 1. For more details on computation of TIs of different chemical structures, the readers can see [29–36].Table 1
Degree-based topological descriptors.
Topological descriptorsMathematical formGeneral RI [19]RαG=∑ab∈EGdadbαGeneral ZI [20]MαG=∑a∈VGdaαGeneral sum-connectivity index [21]χαG=∑ab∈EGda+dbαRI [22, 23]RG=R−12G=∑ab∈EG1/dadbFirst ZI [7]M1G=∑ab∈EGda+dbSecond ZI [7]M2G=∑ab∈EGdadbHyper ZI [24]HMG=∑ab∈EGda+db2First multiplicative ZI [25]PM1G=∏ab∈EGda+dbSecond multiplicative ZI [25]PM2G=∏ab∈EGdadbABC index [26]ABCG=∑ab∈EGda+db−2/dadbGeometric arithmetic [27]GAG=∑ab∈EG2da+db/da+dbFourth version of ABC index [14]ABC4G=∑ab∈EGSa+Sb−2/SaSbFifth version of geometric-arithmetic index [28]GA5G=∑av∈EG2SaSb/Sa+SbIn this paper, we constructed two classes of Benes network, i.e., horizontal cylindrical Benes networkHCBr and vertical cylindrical Benes network VCBr obtained by identification of vertices of first rows with last row and first column with last column of Benes network, respectively. Also, we embed the Benes network on torus denoted by TBr. Figures 2 and 3 show the graph of horizontal and vertical Benes networks, respectively. The graph of embedding of Benes network on torus is shown in Figure 4. We compute Rα, Mα, χα,M1, M2, PM1, PM2, HM, ABC, and GA indices of these networks. Also, the explicit formula of ABC4 and GA5 indices is computed for these networks.Figure 2
3D horizontal cylinderical Benes network.Figure 3
3D vertical cylindrical Benes network.Figure 4
3D toroidal Benes network.


## 2. Results for Cylindrical Representation of Benes Network

In this section, we construct two types of cylindrical Benes network by identifying its vertices. First, we identify the vertices of top row to the vertices of bottom row of Benes networkBr. This will result in a cylindrical network, and we call it a horizontal cylindrical Benes network and denote it by HCBr. Following the construction, a 3-dimensional horizontal cylindrical Benes network HCB3 is presented in Figure 2, where the same label to the vertices represents identification of vertices. Clearly, VHCBr=2r+12r−1 and EHCBr=2r2r+1−1, respectively. Now, we compute the Rα, Mα, and χα of horizontal cylindrical Benes network HCBr.Theorem 1.
Letℋ be the graph of horizontal cylindrical Benes network (HCBr), then(1)Rαℋ=2r+2−128α+8×12α+4r−12r−316α+2×18α+8r−124α+2r−136αMαℋ=22r−22α+2×3α+2r−22r−14α+2r−16α,χαℋ=2r+2−126α+4×7α+4r−12r−3+18α+2×9α+8r−110α+2r−112α.Proof.
In graphℋ, we have 2r+12r−1 vertices among which 22r−2 vertices are of degree 2, 2 vertices are of degree 3, 2r−12r−2 vertices are of degree 4, and the remaining 2r−1 vertices are of degree 6. Now, by using the formula of general Zagreb index, we get(2)Mαℋ=∑a∈Vℋdaα,=22r−22α+2×3α+2r−22r−14α+2r−16α.
To compute theRα and χα indices, we need the partition of the edges of G based on the degree of the end vertices. This partition is given in Table 1. Using the values from Table 1, we can compute the Rα and χα indices as follows:(3)Rαℋ=∑ab∈Eℋdadbα=2r+2−124×2α+4×2×6α+4×3×4α+4r−12r−34×4α+2×3×6α+8r−16×4α+2r−16×6α=2r+2−128α+8×12α+4r−12r−316α+2×18α,χαℋ=∑ab∈Eℋda+dbα=2r+2−122+4α+4×3+4α+4r−12r−34+4α+4×4+4α+2×3+6α+8r−14+6α+2r−16+6α.=2r+2−126α+4×7α+4r−12r−3+18α+2×9α+8r−110α+2r−112α.The values of first Zagreb, second Zagreb, and hyper-Zagreb indices can be computed from the Theorem 6 by taking the value of α=−1/2,1,2.Corollary 1.
Letℋ be the graph of horizontal cylindrical Benes network, then(4)Rℋ=2r2+r−1+31−2+43+23,M1ℋ=2r+34r−1+8r−2,M2ℋ=2r+6r−1+2r+5+72r−36,HMℋ=2r−3256r−112+1088r−474.
Next, we compute thePM1, PM2, ABC, and GA indices of horizontal cylindrical Benes network.Table 2
The partition of edge set ofHCBr built on the degree of end vertices of each edge.
da,db,where ab∈EG(2, 6)(3, 4)(3, 6)(4, 2)(4, 4)Number of edges4422r+2−124r−12r−3da,db, where ab∈EG(4, 6)(6, 6)Number of edges8r−12r−1Theorem 2.
Letℋ be the graph of horizontal cylindrical Benes network, then(5)PM1ℋ=122r−2×1042r−2×62r+2−12×84r−12r−3×796594176,PM2ℋ=362r−2×2442r−2×82r+2−12×164r−12r−3×1.39×1011,ABCℋ=2r−322+6r−1+r−183+103+22+143+253,GAℋ=2r−3823+4r−1+2r−1865+1+23+423+1637.Proof.
The result follows by using the values of the edge partition given in Table2 to the formulas of the PM1, PM2, ABC, and GA indices presented in Table 1.
Now, we compute the valuesABC4 and GA5 indices of HCBr, where r≥4. This requires the partition of its edges based on the sum of degree of neighboring vertices of end vertices of each edge. This partition is given in Table 3.Table 3
Partition of edge set ofHCBr,r≥4, built on degree sum of neighbor vertices of end vertices of each edge.
Sa,Sa,whereuv∈EℋNumber of edges(8, 12)22r+1−1(12, 16)22r+1−1(16, 16)22r+1−1r−2Theorem 3.
Letℋ be the graph of Horizontal cylindrical Benes network HCBr,r≥4, then(6)ABC4ℋ=2r+1−132+264+r−2308,GA5ℋ=2r+1−1465+837+2r−2.Proof.
Letmi,j denotes the number of edges of ℋ with i=Sa and j=Sb. Then, by using Table 3, ABC4 and GA5 indices can be computed as follows:(7)ABC4ℋ=∑ab∈EℋSa+Sb−2Sa×Sb=m8,128+12−28×12+m12,1612+16−212×16+m16,1616+16−216×16=22r+1−18+12−28×12+22r+1−112+16−212×16+22r+1−1r−216+16−216×16=2r+1−132+264+r−2308,GA5ℋ=∑uv∈Eℋ2Sa×SbSa+Sb=m8,1228×128+12+m12,16212×1612+16+m16,16216×1616+16=22r+1−128×128+12+22r+1−1212×1612+16+22r+1−1r−2216×1616+16=2r+1−1465+837+2r−2.This completes the proof.Next, we consider the vertical identification of the vertices. We identify the vertices on the left column with the corresponding vertices on the right column to form a cylindrical network. We name this network as the vertical cylindrical Benes network and denote it byVCBr. The graph of VCB3 is shown in Figure 3, where the arcs from vertical sides represent vertical sides identification. The r-dimensional vertical cylindrical Benes network has r2r+1 vertices and r2r+2 edges. One can see that VCBr is a 4-regular graph. Therefore, the computation of TIs for VCBr is straightforward and is presented in the following theorem.Theorem 4.
LetK be the graph of vertical cylindrical Benes network, then(8)RαK=r24α+r+2,MαK=r22α+r+1,χαK=r23α+r+2,PM1K=23r×2r+2,PM2K=24r×2r+2,ABCK=6r2r,GAK=r2r+2,ABC4K=30r2r−2,GA5K=r2r+2.


## 3. Results for Toroidal Representation of Benes NetworkTBr

If we identify the vertices in the top row ofVCBr to the corresponding vertices of the bottom row, we get a toroidal network. We call this network Toroidal Benes network and denote it by TBr. Figure 4 shows the graph of toroidal Benes network TB3. Clearly, VTBr=2r+12r−1 and ETBr=2r2r+1−1, respectively. Now, we compute the Rα, χα, and Mα of toroidal Benes network TBr.Theorem 5.
Letℒ be the graph of toroidal cylindrical Benes network, then(9)Rαℒ=2r2r+1−6×16α+8r×24α+2r×36α,Mαℒ=2r2r−2×4α+2r×6α,χαℒ=2r2r+1−6×8α+8r×10α+2r×12α.Proof.
In graphℒ, we have 2r+12r−1 vertices among which 2r2r−2 vertices are of degree 4 and the remaining 2r vertices are of degree 6. By using the formula of general Zagreb index, we get(10)Mαℒ=∑uv∈Eℒduα=2r2r−2×4α+2r×6α.
To compute the general Randic and general sum connectivity indices, we need the partition of the edges ofℒ based on the degree of the end vertices. This partition is given in Table 4. Using the values from Table 4, we can compute the Randic and general sum connectivity indices as follows:(11)Rαℒ=∑ab∈Eℒdadbα=2r2r+1−64×4α+8r×4×6α+2r×6×6α=2r2r+1−6×16α+8r×24α+2r×36α,χαℒ=∑ab∈Eℒda+dbα=2r2r+1−64+4α+8r×4+6α+2r6+6α=2r2r+1−6×8α+8r×10α+2r×12α.
The values of first Zagreb, second Zagreb, and hyper-Zagreb indices can be computed from the Theorem 6 by taking value ofα=−1/2,1 and 2.Table 4
Partition of edge set ofTBr built on the degree of end vertices of each edge.
(da,db),where uv∈EℒNumber of edges(4, 4)2r2r+1−6(4, 6)8r(6, 6)2rCorollary 2.
Letℒ be the graph of toroidal Benes network, then(12)Rℒ=2r2r−1−43+26,M1ℒ=8r2r+2+1,M2ℒ=8r2r+3+9,HMℒ=8r2r+5+40.Next, we compute the exact values of first multiple Zagreb, second multiple Zagreb, and ABC and GA indices of horizontal cylindrical Benes network.Theorem 6.
Letℒ be the graph of toroidal Benes network, then(13)PM1ℒ=82r2r+1−6×108r×122r,PM2ℒ=162r2r+1−6×248r×362r,ABCℒ=r2r+1−66+8r26+r103,GAℒ=2r2r+1−5+16r65.Proof.
The result follows by using the values of the edge partition given in Table4 to the formulas of the PM1, PM2, ABC, and GA indices presented in Table 1.Now, we compute the values ofABC4 and GA5 indices of TBr, where r≥4. This requires the partition of its edges based on the sum of degree of neighboring vertices of end vertices of each edge. This partition is given in Table 5.Table 5
The edge partition of graphTBr,r≥4, based on degree sum of neighbor vertices of end vertices of each edge.
Sa,Sb,whereab∈EℒNumber of edges(8, 12)22r+1−1(12, 16)22r+1−1(16, 16)22r+1−1r−2Theorem 7.
Letℒ be the graph of toroidal Benes network TBr,r≥4, then(14)ABC4ℒ=2r+1−132+264+r−2308,GA5ℒ=2r+1−1465+837+2r−2.Proof.
Letmi,j denote the number of edges of G with i=Sa and j=Sb. Then, by using Table 5, ABC4 and GA5 indices can be computed as follows:(15)ABC4ℒ=∑ab∈EℒSa+Sb−2Sa×Sb=m8,128+12−28×12+m12,1612+16−212×16+m16,1616+16−216×16=22r+1−18+12−28×12+22r+1−112+16−212×16+22r+1−1r−216+16−216×16=2r+1−132+264+r−2308,GA5ℒ=∑ab∈Eℒ2Sa×SbSa+Sb=m8,1228×128+12+m12,16212×1612+16+m16,16216×1616+16=22r+1−128×128+12+22r+1−1212×1612+16+22r+1−1r−2216×1616+16,=2r+1−1465+837+2r−2.
This completes the proof.


## 4. Conclusion and General Remarks

Designing new network structure always attract and open ways for the researchers in the networking and other structural sciences. In this paper, we constructed new classes of Benes networks embedded on the surface of cylinder and torus called horizontal cylindrical Benes networkHCBr, vertical cylindrical Benes network VCBr, and toroidal Benes network TBr. Then, some degree-based TIs are studied for the abovementioned networks. In future, it will help to those who are interested in problems related to interconnected networks and will be able to deal with the complex networks and their topological properties.



---

*Source: 6690053-2021-01-19.xml*