# Irregularity of Block Shift Networks and Hierarchical Hypercube Networks

Authors: Juanyan Fang; Iftikhar Ahmed; Abid Mehboob; Kashif Nazar; Haseeb Ahmad
Journal: Journal of Chemistry
 (2019)

---

## Abstract

There is extremely a great deal of mathematics associated with electrical and electronic engineering. It relies upon what zone of electrical and electronic engineering; for instance, there is much increasingly theoretical mathematics in communication theory, signal processing and networking, and so forth. Systems include hubs speaking with one another. A great deal of PCs connected together structure a system. Mobile phone clients structure a network. Networking includes the investigation of the most ideal method for executing a system. Graph theory has discovered a significant use in this zone of research. In this paper, we stretch out this examination to interconnection systems. Hierarchical interconnection systems (HINs) give a system to planning systems with diminished connection cost by exploiting the area of correspondence that exists in parallel applications. HINs utilize numerous levels. Lower-level systems give nearby correspondence, while more significant level systems encourage remote correspondence. HINs provide issue resilience within the sight of some defective nodes and additionally interfaces. Existing HINs can be comprehensively characterized into two classes: those that use nodes or potential interface replication and those that utilize reserve interface nodes.


---

## Body

## 1. Introduction

Graph theory has many applications in chemistry, physics, computer sciences, and other applied sciences [1–9]. Multiprocessor interconnection networks (MINs) are required to connect processor-memory pairs, each of which is known as the processing node. Design and usage of MINs have gained remarkable attention because of the availability of powerful microprocessors and memory chips and also due to its low cost [10, 11]. Hierarchical interconnection network (HIN) [12] is a framework for designing new networks that decrease link cost and has applications in parallel communications. The multistage networks have applications as communication networks for parallel computing [12–14]. For details about graph theory, we recommend the references [15–19].Throughout this article, all graphs are finite, undirected, and simple. LetG=VG,EG be such a graph with vertex set VG and edge set EG. The order of G is the cardinality of its vertex set, and size is the cardinality of its edge set. In a network, the vertices of G correspond to node, and an edge between two vertices is the link between these vertices. The degree of a vertex u of a graph G is symbolized by du and is defined as the number of edges incident with u. A graph is said to be regular, if all its vertices have the same degree; otherwise, it is irregular.For the first time in history, Chartrand et al. [20] underlined the study of irregular graphs. From that point forward, the irregularity degree and irregular graphs have turned into the essential open issue of graph theory. A graph is said to be a perfect graph if all the vertices have different degrees (i.e., no two vertices have the same degree). The fact no graph is perfect is proved in [21]. The graphs lying in the middle are called semiperfect (quasiperfect) graphs, in which each, aside from the two vertices, has various degrees [22]. The irregularity indices give the best knowledge about the irregularity of graph and have been studied extensively in the literature [23, 24]. The primary irregularity index was presented in [25]. The Albertson index, ALG, was introduced by Albertson in [26] as follows:(1)ALG=∑uv∈EGdu−dv.The irregularity indexes IRL (G) and IRLU (G) are defined by Vukičević and Graovac [27] as follows:(2)IRLG=∑uv∈EGlndu−lndv,IRLUG=∑uv∈EGdu−dvmindu,dv.Recently, Abdo and Dimitrov [28] established the new idea of “total irregularity measure of a graph G,” which was lately discussed in [29, 30]. The Randić index itself is directly associated with an irregularity determination [31] as follows:(3)IRAG=∑uv∈EGdu−1/2−dv−1/22.Further irregularity indices of comparative nature can be followed in [30] in detail, and for the applications of indices in chemistry, we refer [31–42]. In [43], irregularity indices of nanotubes were determined. Gao et al. [44] computed irregularity measures of some dendrimers, and the same was computed for different molecular structures in [45]. In [46], irregularity measures for some classes of benzenoid systems were computed.Irregularity indices investigated in this paper are given in Table1. For the undefined notion in Table 1, we refer [47–52]. All of them belong to the family of degree-based irregularity indices.Table 1
Irregularity indices.
VAR
G
=
M
1
G
/
n
−
2
m
/
n
2
IRC
G
=
RR
G
/
m
−
2
m
/
n
AL
G
=
∑
u
v
∈
E
G
d
u
−
d
v
IRDIF
G
=
∑
u
v
∈
E
G
d
u
/
d
v
−
d
v
/
d
u
IR
1
G
=
F
G
−
2
m
/
n
M
1
G
IRL
G
=
∑
u
v
∈
E
G
ln
d
u
−
ln
d
v
IR
2
G
=
M
2
G
/
m
−
2
m
/
n
IRLU
G
=
∑
u
v
∈
E
G
d
u
−
d
v
/
min
d
u
,
d
v
IRF
G
=
F
G
−
2
M
2
G
IRLF
G
=
∑
u
v
∈
E
G
d
u
−
d
v
/
d
u
×
d
v
IRFW
G
=
IRF
G
/
M
2
G
IRLA
G
=
∑
u
v
∈
E
G
2
d
u
−
d
v
/
d
u
+
d
v
IRA
G
=
∑
u
v
∈
E
G
d
u
−
1
/
2
−
d
v
−
1
/
2
2
IRD
1
G
=
∑
u
v
∈
E
G
ln
1
+
d
u
−
d
v
IRB
G
=
∑
u
v
∈
E
G
d
u
1
/
2
−
d
v
1
/
2
2
IRGA
G
=
∑
u
v
∈
E
G
ln
d
u
+
d
v
/
2
d
u
×
d
v


## 2. Methodology

LetG=VG,EG be such a graph with vertex set VG and edge set EG. We use edge partition to find irregularity indices, and edge partition depends on the degree of end vertices of edges. Edges are partitioned by the same and different degrees of vertices hold edges.


### 2.1. Results for Block Shift Network (BSN)

The block shift network can be denoted byBSN and was firstly introduced in 1991 by Pan and Chuang [53]. These are interconnection networks, and due to its hypercube topology, it has many benefits. The idea to design this network is to have a linkage in certain dimensions in order to make it a comparable performance and reduce number of links. The topology of BSN fulfils the requirements of the communication algorithms. BSN surpasses the hypercube in several respects while retaining most of its advantages, especially when the traffic has the locality property [54]. Many existing networks can be considered as special cases of BSN. For example, BSN−1 is the shuffle-exchange network with n-dimensional hypercube, while BSN−2 is the complete network, as shown in Figures 1 and 2, respectively. Let G be a block shift network. It can be seen from Figure 1 that the number of vertices and edges in BSN−1 are 16a2 and 24a2−2, respectively. From Figure 2, one can observe that the number of vertices and edges in BSN−2 are 16a2 and 32a2−2, respectively.Figure 1
BSN
−
1
3
×
3.Figure 2
BSN
−
2
1
×
1.Theorem 1.
For the block shift networkBSN−1, we have(1)
VARBSN−1=4a2−1/16a4(2)
ALBSN−1=8(3)
IR1BSN−1=54a2−1/a2(4)
IR2BSN−1=6216a2−42/624a2−2−48a2−4/16a2(5)
IRFBSN−1=8(6)
IRFWBSN−1=4/108a2−21(7)
IRABSN−1=1213215869760357/9007199254740992(8)
IRBBSN−1=909911902320267/1125899906842624(9)
IRCBSN−1=−36a2−166a2+1/4a212a2−1(10)
IRDIFBSN−1=20/3(11)
IRLBSN−1=3652105019575333/1125899906842624(12)
IRLUBSN−1=4(13)
IRLFBSN−1=46/3(14)
IRLABSN−1=16/5(15)
IRD1BSN−1=6243314768165359/1125899906842624(16)
IRGABSN−1=2941534708959071/18014398509481984Proof.
The order of graph isn=VBSN−1=16a2, and its size is m=EBSN−1=24a2−2. The vertex set of BSN−1 can be divided into the following classes by means of degrees:(4)V1BSN−1=v∈VBSN−1:du=2,V2BSN−1=v∈VBSN−1:du=3.
The edge set ofBSN−1 can be divided into the following classes with respect to the degrees of end vertices:(5)E1BSN−1=uv∈EBSN−1:du=dv=3,E2BSN−1=uv∈EBSN−1:du=2,dv=3.
And the cardinality of edges is as follows:(6)E1BSN−1=24a2−10,E2BSN−1=8.
First, we find some topological indices, which will be used in irregularity indices:(7)M1BSN−1=144a2−20,M2BSN−1=216a2−42,FBSN−1=432a2−76,RRBSN−1=72a2+86−30.
Now, by definitions given in Table1, we have(8)VARBSN−1=M1BSN−1n−2mn2=144a2−2016a2−224a2−216a22=4a2−116a4.(9)ALBSN−1=∑uv∈EBSN−1du−dv=∑uv∈E1BSN−10+∑uv∈E2BSN−12−3=8.(10)IR1BSN−1=FBSN−1−2mnM1BSN−1=432a2−76−224a2−216a2144a2−20=54a2−1a2.(11)IR2BSN−1=M2BSN−1m−2mn=216a2−4224a2−2−224a2−216a2=6216a2−42624a2−2−48a2−416a2.(12)IRFBSN−1=FBSN−1−2M2BSN−1=432a2−76−2216a2−42=8.(13)IRFWBSN−1=IRFBSN−1M2BSN−1=8216a2−42=8.(14)IRABSN−1=∑uv∈EBSN−1du−1/2−dv−1/22=∑uv∈E1BSN−10+∑uv∈E2BSN−12−1/2−3−1/22=12132158697603579007199254740992.(15)IRBBSN−1=∑uv∈EBSN−1du1/2−dv1/22=∑uv∈E1BSN−10+∑uv∈E2BSN−121/2−31/22=9099119023202671125899906842624.(16)IRCBSN−1=RRBSN−1m−2mn=72a2+86−3024a2−2−224a2−216a2=−36a2−166a2+14a212a2−1.(17)IRDIFBSN−1=∑uv∈EBSN−1dudv−dvdu=∑uv∈E1BSN−10+∑uv∈E2BSN−123−32=203.(18)IRLBSN−1=∑uv∈EBSN−1lndu−lndv=∑uv∈E1BSN−10+∑uv∈E2BSN−1ln2−ln3=36521050195753331125899906842624.(19)IRLUBSN−1=∑uv∈EBSN−1du−dvmindu,dv=∑uv∈E1BSN−10+∑uv∈E2BSN−12−3min2,3=4.(20)IRLFBSN−1=∑uv∈EBSN−1du−dvdu×dv=∑uv∈E1BSN−10+∑uv∈E2BSN−12−32×3=463.(21)IRLABSN−1=∑uv∈EBSN−12du−dvdu+dv=∑uv∈E1BSN−10+∑uv∈E2BSN−122−32+3=165.(22)IRD1BSN−1=∑uv∈EBSN−1ln1+du−dv=∑uv∈E1BSN−10+∑uv∈E2BSN−1ln1+2−3=62433147681653591125899906842624.(23)IRGABSN−1=∑uv∈EBSN−1lndu+dv2du×dv=∑uv∈E1BSN−10+∑uv∈E2BSN−1ln2+322×3=294153470895907118014398509481984.Theorem 2.
For the block shift networkBSN−2, we have(1)
VARBSN−2=4a2−1/16a4(2)
ALBSN−2=12(3)
IR1BSN−2=74a2−1/a2(4)
IR2BSN−2=4512a2−80/1632a2−2−64a2−4/16a2(5)
IRFBSN−2=12(6)
IRFWBSN−2=3/128a2−20(7)
IRABSN−2=20694009944167803/288230376151711744(8)
IRBBSN−2=15520507458125877/18014398509481984(9)
IRCBSN−2=−80a2−483a2+1/4a216a2−1(10)
IRDIFBSN−2=7(11)
IRLBSN−2=3886814622885039/1125899906842624(12)
IRLUBSN−2=4(13)
IRLFBSN−2=23(14)
IRLABSN−2=24/7(15)
IRD1BSN−2=18729944304496077/2251799813685248(16)
IRGABSN−2=2228664339909267/18014398509481984Proof.
The order of graph isn=VBSN−2=16a2, and its size is m=EBSN−2=32a2−2. The vertex set of BSN−2 can be divided into the following classes by means of degrees:(24)V1BSN−2=v∈VBSN−2:du=3,V2BSN−2=v∈VBSN−2:du=4.
The edge set ofBSN−2 can be divided into the following classes with respect to the degrees of end vertices:(25)E1BSN−2=uv∈EBSN−2:du=dv=4,E2BSN−2=uv∈EBSN−2:du=3,dv=4.
And the cardinality of edges is as follows:(26)E1BSN−2=32a2−14,E2BSN−2=12.
First, we find some topological indices, which will be used in irregularity indices:(27)M1BSN−2=256a2−28,M2BSN−2=512a2−80,FBSN−2=1024a2−148,RRBSN−2=128a2+243−56.
Now, from the definitions given in Table1, we have(28)VARBSN−2=M1BSN−2n−2mn2=256a2−2816a2−232a2−216a22=4a2−116a4.(29)ALBSN−2=∑uv∈EBSN−2du−dv=∑uv∈E1BSN−20+∑uv∈E2BSN−23−4=12.(30)IR1BSN−2=FBSN−2−2mnM1BSN−2=1024a2−148−232a2−216a2256a2−28=74a2−1a2.(31)IR2BSN−2=M2BSN−2m−2mn=512a2−8032a2−2−232a2−216a2=4512a2−801632a2−2−64a2−416a2.(32)IRFBSN−2=FBSN−2−2M2BSN−2=1024a2−148−2512a2−80=12.(33)IRFWBSN−2=IRFBSN−2M2BSN−2=12512a2−80=12.(34)IRABSN−2=∑uv∈EBSN−2du−1/2−dv−1/22=∑uv∈E1BSN−20+∑uv∈E2BSN−23−1/2−4−1/22=20694009944167803288230376151711744.(35)IRBBSN−2=∑uv∈EBSN−2du1/2−dv1/22=∑uv∈E1BSN−20+∑uv∈E2BSN−231/2−41/22=1552050745812587718014398509481984.(36)IRCBSN−2=RRBSN−2m−2mn=128a2+243−5632a2−2−232a2−216a2=−80a2−483a2+14a216a2−1.(37)IRDIFBSN−2=∑uv∈EBSN−2dudv−dvdu=∑uv∈E1BSN−20+∑uv∈E2BSN−234−43=7.(38)IRLBSN−2=∑uv∈EBSN−2lndu−lndv=∑uv∈E1BSN−20+∑uv∈E2BSN−2ln3−ln4=38868146228850391125899906842624.(39)IRLUBSN−2=∑uv∈EBSN−2du−dvmindu,dv=∑uv∈E1BSN−20+∑uv∈E2BSN−23−4min3,4=4.(40)IRLFBSN−2=∑uv∈EBSN−2du−dvdu×dv=∑uv∈E1BSN−20+∑uv∈E2BSN−23−43×4=23.(41)IRLABSN−2=∑uv∈EBSN−22du−dvdu+dv=∑uv∈E1BSN−20+∑uv∈E2BSN−223−43+4=247.(42)IRD1BSN−2=∑uv∈EBSN−2ln1+du−dv=∑uv∈E1BSN−20+∑uv∈E2BSN−2ln1+3−4=187299443044960772251799813685248.(43)IRGABSN−2=∑uv∈EBSN−2lndu+dv2du×dv=∑uv∈E1BSN−20+∑uv∈E2BSN−2ln3+423×4=222866433990926718014398509481984.


### 2.2. Results for Hierarchical Hypercube NetworkHHC

Hierarchical hypercube networkHHC has many features, for example, symmetry and logarithmic diameter, which imply easy and fast algorithms for communication [55]. The structure of an n-HHC consists of three levels of hierarchy. At the lowest level of hierarchy, there is a pool of 2n nodes. These nodes are grouped into clusters of 2m nodes each, and the nodes in each cluster are interconnected to form an m−cube called the son cube or the S-cube. The set of the S-cubes constitutes the second level of hierarchy [56].Due to the hierarchical structure,HHC has the advantages that are gained by hierarchy. “In addition, hierarchical structures are capable of exploiting the locality of reference (communication), and they are fault tolerant. Other attractive properties of the HHC structure are logarithmic diameter and a topology inherited from, and closely related to, the hypercube topology. The former property implies fast communication, and the latter implies easy mapping of operations from HC to HHC. The HHC can emulate the hypercube for a large class of problems (divide conquer), without a significant increase in processing time. The HHC can embed rings and HHCs of lower dimension. In addition, HHC embeds the cube connected cycles CCC [57].” As a result, the performance of HHC is in the worst case equivalent to the performance of the CCC.The number of vertices and edges inHHC−1 are 16a+16 and 24a+20, respectively. The number of vertices and edges in HHC−2 are 16a+16 and 32a+28, respectively. HHC−1 and HHC−2 are shown in Figures 3 and 4, respectively.Figure 3
HHC
−
1
1
×
1.Figure 4
HHC
−
2
1
×
1.Theorem 3.
For the hierarchical hypercube networkHHC−1, we have(1)
VARHHC−1=2a+1/4a+12(2)
ALHHC−1=16(3)
IR1HHC−1=202a+1/a+1(4)
IR2HHC−1=2318a+11/24a+20−6a+5/2a+1(5)
IRFHHC−1=16(6)
IRFWHHC−1=4/54a+33(7)
IRAHHC−1=1213215869760357/4503599627370496(8)
IRBHHC−1=909911902320267/562949953421312(9)
IRCHHC−1=72a+166+12/24a+20−48a+40/16a+16(10)
IRDIFHHC−1=40/3(11)
IRLHHC−1=3652105019575333/562949953421312(12)
IRLUHHC−1=8(13)
IRLFHHC−1=86/3(14)
IRLAHHC−1=32/5(15)
IRD1HHC−1=6243314768165359/562949953421312(16)
IRGAHHC−1=2941534708959071/9007199254740992Proof.
The order of graph isn=VHHC−1=16a+16, and its size is m=EHHC−1=24a+20. The vertex set of HHC−1 can be divided into the following classes by means of degrees:(44)V1HHC−1=v∈VHHC−1:du=2,V2HHC−1=v∈VHHC−1:du=3.
The edge set ofHHC−1 can be divided into the following classes with respect to the degrees of end vertices:(45)E1HHC−1=uv∈EHHC−1:du=dv=3,E2HHC−1=uv∈EHHC−1:du=2,dv=3.
And the cardinality of edges is as follows:(46)E1HHC−1=24a+4,E2HHC−1=16.
First, we find some topological indices, which will be used in irregularity indices:(47)M1HHC−1=144a+104,M2HHC−1=216a+132,FHHC−1=432a+280,RRHHC−1=72a+166+12.
Now from definitions, we have(48)VARHHC−1=M1HHC−1n−2mn2=144a+10416a+16−224a+2016a+162=2a+14a+12.(49)ALHHC−1=∑uv∈EHHC−1du−dv=∑uv∈E1HHC−10+∑uv∈E2HHC−12−3=16.(50)IR1HHC−1=FHHC−1−2mnM1HHC−1=432a+280−224a+2016a+16144a+104=202a+1a+1.(51)IR2HHC−1=M2HHC−1m−2mn=216a+13224a+20−224a+2016a+16=2318a+1124a+20−6a+52a+1.(52)IRFHHC−1=FHHC−1−2M2HHC−1=432a+280−2216a+132=16.(53)IRFWHHC−1=IRFHHC−1M2HHC−1=16216a+132=16.(54)IRAHHC−1=∑uv∈EHHC−1du−1/2−dv−1/22=∑uv∈E1HHC−10+∑uv∈E2HHC−12−1/2−3−1/22=12132158697603574503599627370496.(55)IRCHHC−1=RRHHC−1m−2mn=72a+166+1224a+20−224a+2016a+16=72a+166+1224a+20−48a+4016a+16.(56)IRDIFHHC−1=∑uv∈EHHC−1dudv−dvdu=∑uv∈E1HHC−10+∑uv∈E2HHC−123−32=403.(57)IRLHHC−1=∑uv∈EHHC−1lndu−lndv=∑uv∈E1HHC−10+∑uv∈E2HHC−1ln2−ln3=3652105019575333562949953421312.(58)IRLUHHC−1=∑uv∈EHHC−1du−dvmindu,dv=∑uv∈E1HHC−10+∑uv∈E2HHC−12−3min2,3=8.(59)IRLFHHC−1=∑uv∈EHHC−1du−dvdu×dv=∑uv∈E1HHC−10+∑uv∈E2HHC−12−32×3=863.(60)IRLAHHC−1=∑uv∈EHHC−12du−dvdu+dv=∑uv∈E1HHC−10+∑uv∈E2HHC−122−32+3=325.(61)IRD1HHC−1=∑uv∈EHHC−1ln1+du−dv=∑uv∈E1HHC−10+∑uv∈E2HHC−1ln1+2−3=6243314768165359562949953421312.(62)IRGAHHC−1=∑uv∈EHHC−1lndu+dv2du×dv=∑uv∈E1HHC−10+∑uv∈E2HHC−1ln2+322×3=29415347089590719007199254740992.Theorem 4.
For the hierarchical hypercube networkHHC−2, we have(1)
VARHHC−2=2a+1/4a+12(2)
ALHHC−2=24(3)
IR1HHC−2=282a+1/a+1(4)
IR2HHC−2=4216a+11/32a+28−8a+7/2a+1(5)
IRFHHC−2=24(6)
IRFWHHC−2=3/64a+44(7)
IRAHHC−2=20694009944167803/144115188075855872(8)
IRBHHC−2=15520507458125877/9007199254740992(9)
IRCHHC−2=128a+483+16/32a+28−64a+56/16a+16(10)
IRDIFHHC−2=14(11)
IRLHHC−2=3886814622885039/562949953421312(12)
IRLUHHC−2=8(13)
IRLFHHC−2=43(14)
IRLAHHC−2=48/7(15)
IRD1HHC−2=18729944304496077/1125899906842624(16)
IRGAHHC−2=2228664339909267/9007199254740992Proof.
The order of graph isn=VHHC−2=16a+16, and its size is m=EHHC−2=32a+28. The vertex set of HHC−2 can be divided into the following classes by means of degrees:(63)V1HHC−2=v∈VHHC−2:du=3,V2HHC−2=v∈VHHC−2:du=4.
The edge set ofHHC−2 can be divided into the following classes with respect to the degrees of end vertices:(64)E1HHC−2=uv∈EHHC−2:du=dv=4,E2HHC−2=uv∈EHHC−2:du=3,dv=4.
And the cardinality of edges is as follows:(65)E1HHC−2=32a+4,E2HHC−2=24.
First, we find some topological indices, which will be used in irregularity indices:(66)M1HHC−2=256a+200,M2HHC−2=512a+352,FHHC−2=1024a+728,RRHHC−2=128a+483+16.
Now, from definitions, we have(67)VARHHC−2=M1HHC−2n−2mn2=256a+20016a+16−232a+2816a+162=2a+14a+12.(68)ALHHC−2=∑uv∈EHHC−2du−dv=∑uv∈E1HHC−20+∑uv∈E2HHC−23−4=24.(69)IR1HHC−2=FHHC−2−2mnM1HHC−2=1024a+728−232a+2816a+16256a+200=282a+1a+1.(70)IR2HHC−2=M2HHC−2m−2mn=512a+35232a+28−232a+2816a+16=4216a+1132a+28−8a+72a+1.(71)IRFHHC−2=FHHC−2−2M2HHC−2=1024a+728−2512a+352=24.(72)IRFWHHC−2=IRFHHC−2M2HHC−2=24512a+352=24.(73)IRAHHC−2=∑uv∈EHHC−2du−1/2−dv−1/22=∑uv∈E1HHC−20+∑uv∈E2HHC−23−1/2−4−1/22=20694009944167803144115188075855872.(74)IRBHHC−2=∑uv∈EHHC−2du1/2−dv1/22=∑uv∈E1HHC−20+∑uv∈E2HHC−231/2−41/22=155205074581258779007199254740992.(75)IRCHHC−2=RRHHC−2m−2mn=128a+483+1632a+28−232a+2816a+16=128a+483+1632a+28−64a+5616a+16.(76)IRDIFHHC−2=∑uv∈EHHC−2dudv−dvdu=∑uv∈E1HHC−20+∑uv∈E2HHC−234−43=14.(77)IRLHHC−2=∑uv∈EHHC−2lndu−lndv=∑uv∈E1HHC−20+∑uv∈E2HHC−2ln3−ln4=3886814622885039562949953421312.(78)IRLUHHC−2=∑uv∈EHHC−2du−dvmindu,dv=∑uv∈E1HHC−20+∑uv∈E2HHC−23−4min3,4=8.(79)IRLFHHC−2=∑uv∈EHHC−2du−dvdu×dv=∑uv∈E1HHC−20+∑uv∈E2HHC−23−43×4=43.(80)IRLAHHC−2=∑uv∈EHHC−22du−dvdu+dv=∑uv∈E1HHC−20+∑uv∈E2HHC−223−43+4=487.(81)IRD1HHC−2=∑uv∈EHHC−2ln1+du−dv=∑uv∈E1HHC−20+∑uv∈E2HHC−2ln1+3−4=187299443044960771125899906842624.(82)IRGAHHC−2=∑uv∈EHHC−2lndu+dv2du×dv=∑uv∈E1HHC−20+∑uv∈E2HHC−2ln3+423×4=22286643399092679007199254740992.


## 2.1. Results for Block Shift Network (BSN)

The block shift network can be denoted byBSN and was firstly introduced in 1991 by Pan and Chuang [53]. These are interconnection networks, and due to its hypercube topology, it has many benefits. The idea to design this network is to have a linkage in certain dimensions in order to make it a comparable performance and reduce number of links. The topology of BSN fulfils the requirements of the communication algorithms. BSN surpasses the hypercube in several respects while retaining most of its advantages, especially when the traffic has the locality property [54]. Many existing networks can be considered as special cases of BSN. For example, BSN−1 is the shuffle-exchange network with n-dimensional hypercube, while BSN−2 is the complete network, as shown in Figures 1 and 2, respectively. Let G be a block shift network. It can be seen from Figure 1 that the number of vertices and edges in BSN−1 are 16a2 and 24a2−2, respectively. From Figure 2, one can observe that the number of vertices and edges in BSN−2 are 16a2 and 32a2−2, respectively.Figure 1
BSN
−
1
3
×
3.Figure 2
BSN
−
2
1
×
1.Theorem 1.
For the block shift networkBSN−1, we have(1)
VARBSN−1=4a2−1/16a4(2)
ALBSN−1=8(3)
IR1BSN−1=54a2−1/a2(4)
IR2BSN−1=6216a2−42/624a2−2−48a2−4/16a2(5)
IRFBSN−1=8(6)
IRFWBSN−1=4/108a2−21(7)
IRABSN−1=1213215869760357/9007199254740992(8)
IRBBSN−1=909911902320267/1125899906842624(9)
IRCBSN−1=−36a2−166a2+1/4a212a2−1(10)
IRDIFBSN−1=20/3(11)
IRLBSN−1=3652105019575333/1125899906842624(12)
IRLUBSN−1=4(13)
IRLFBSN−1=46/3(14)
IRLABSN−1=16/5(15)
IRD1BSN−1=6243314768165359/1125899906842624(16)
IRGABSN−1=2941534708959071/18014398509481984Proof.
The order of graph isn=VBSN−1=16a2, and its size is m=EBSN−1=24a2−2. The vertex set of BSN−1 can be divided into the following classes by means of degrees:(4)V1BSN−1=v∈VBSN−1:du=2,V2BSN−1=v∈VBSN−1:du=3.
The edge set ofBSN−1 can be divided into the following classes with respect to the degrees of end vertices:(5)E1BSN−1=uv∈EBSN−1:du=dv=3,E2BSN−1=uv∈EBSN−1:du=2,dv=3.
And the cardinality of edges is as follows:(6)E1BSN−1=24a2−10,E2BSN−1=8.
First, we find some topological indices, which will be used in irregularity indices:(7)M1BSN−1=144a2−20,M2BSN−1=216a2−42,FBSN−1=432a2−76,RRBSN−1=72a2+86−30.
Now, by definitions given in Table1, we have(8)VARBSN−1=M1BSN−1n−2mn2=144a2−2016a2−224a2−216a22=4a2−116a4.(9)ALBSN−1=∑uv∈EBSN−1du−dv=∑uv∈E1BSN−10+∑uv∈E2BSN−12−3=8.(10)IR1BSN−1=FBSN−1−2mnM1BSN−1=432a2−76−224a2−216a2144a2−20=54a2−1a2.(11)IR2BSN−1=M2BSN−1m−2mn=216a2−4224a2−2−224a2−216a2=6216a2−42624a2−2−48a2−416a2.(12)IRFBSN−1=FBSN−1−2M2BSN−1=432a2−76−2216a2−42=8.(13)IRFWBSN−1=IRFBSN−1M2BSN−1=8216a2−42=8.(14)IRABSN−1=∑uv∈EBSN−1du−1/2−dv−1/22=∑uv∈E1BSN−10+∑uv∈E2BSN−12−1/2−3−1/22=12132158697603579007199254740992.(15)IRBBSN−1=∑uv∈EBSN−1du1/2−dv1/22=∑uv∈E1BSN−10+∑uv∈E2BSN−121/2−31/22=9099119023202671125899906842624.(16)IRCBSN−1=RRBSN−1m−2mn=72a2+86−3024a2−2−224a2−216a2=−36a2−166a2+14a212a2−1.(17)IRDIFBSN−1=∑uv∈EBSN−1dudv−dvdu=∑uv∈E1BSN−10+∑uv∈E2BSN−123−32=203.(18)IRLBSN−1=∑uv∈EBSN−1lndu−lndv=∑uv∈E1BSN−10+∑uv∈E2BSN−1ln2−ln3=36521050195753331125899906842624.(19)IRLUBSN−1=∑uv∈EBSN−1du−dvmindu,dv=∑uv∈E1BSN−10+∑uv∈E2BSN−12−3min2,3=4.(20)IRLFBSN−1=∑uv∈EBSN−1du−dvdu×dv=∑uv∈E1BSN−10+∑uv∈E2BSN−12−32×3=463.(21)IRLABSN−1=∑uv∈EBSN−12du−dvdu+dv=∑uv∈E1BSN−10+∑uv∈E2BSN−122−32+3=165.(22)IRD1BSN−1=∑uv∈EBSN−1ln1+du−dv=∑uv∈E1BSN−10+∑uv∈E2BSN−1ln1+2−3=62433147681653591125899906842624.(23)IRGABSN−1=∑uv∈EBSN−1lndu+dv2du×dv=∑uv∈E1BSN−10+∑uv∈E2BSN−1ln2+322×3=294153470895907118014398509481984.Theorem 2.
For the block shift networkBSN−2, we have(1)
VARBSN−2=4a2−1/16a4(2)
ALBSN−2=12(3)
IR1BSN−2=74a2−1/a2(4)
IR2BSN−2=4512a2−80/1632a2−2−64a2−4/16a2(5)
IRFBSN−2=12(6)
IRFWBSN−2=3/128a2−20(7)
IRABSN−2=20694009944167803/288230376151711744(8)
IRBBSN−2=15520507458125877/18014398509481984(9)
IRCBSN−2=−80a2−483a2+1/4a216a2−1(10)
IRDIFBSN−2=7(11)
IRLBSN−2=3886814622885039/1125899906842624(12)
IRLUBSN−2=4(13)
IRLFBSN−2=23(14)
IRLABSN−2=24/7(15)
IRD1BSN−2=18729944304496077/2251799813685248(16)
IRGABSN−2=2228664339909267/18014398509481984Proof.
The order of graph isn=VBSN−2=16a2, and its size is m=EBSN−2=32a2−2. The vertex set of BSN−2 can be divided into the following classes by means of degrees:(24)V1BSN−2=v∈VBSN−2:du=3,V2BSN−2=v∈VBSN−2:du=4.
The edge set ofBSN−2 can be divided into the following classes with respect to the degrees of end vertices:(25)E1BSN−2=uv∈EBSN−2:du=dv=4,E2BSN−2=uv∈EBSN−2:du=3,dv=4.
And the cardinality of edges is as follows:(26)E1BSN−2=32a2−14,E2BSN−2=12.
First, we find some topological indices, which will be used in irregularity indices:(27)M1BSN−2=256a2−28,M2BSN−2=512a2−80,FBSN−2=1024a2−148,RRBSN−2=128a2+243−56.
Now, from the definitions given in Table1, we have(28)VARBSN−2=M1BSN−2n−2mn2=256a2−2816a2−232a2−216a22=4a2−116a4.(29)ALBSN−2=∑uv∈EBSN−2du−dv=∑uv∈E1BSN−20+∑uv∈E2BSN−23−4=12.(30)IR1BSN−2=FBSN−2−2mnM1BSN−2=1024a2−148−232a2−216a2256a2−28=74a2−1a2.(31)IR2BSN−2=M2BSN−2m−2mn=512a2−8032a2−2−232a2−216a2=4512a2−801632a2−2−64a2−416a2.(32)IRFBSN−2=FBSN−2−2M2BSN−2=1024a2−148−2512a2−80=12.(33)IRFWBSN−2=IRFBSN−2M2BSN−2=12512a2−80=12.(34)IRABSN−2=∑uv∈EBSN−2du−1/2−dv−1/22=∑uv∈E1BSN−20+∑uv∈E2BSN−23−1/2−4−1/22=20694009944167803288230376151711744.(35)IRBBSN−2=∑uv∈EBSN−2du1/2−dv1/22=∑uv∈E1BSN−20+∑uv∈E2BSN−231/2−41/22=1552050745812587718014398509481984.(36)IRCBSN−2=RRBSN−2m−2mn=128a2+243−5632a2−2−232a2−216a2=−80a2−483a2+14a216a2−1.(37)IRDIFBSN−2=∑uv∈EBSN−2dudv−dvdu=∑uv∈E1BSN−20+∑uv∈E2BSN−234−43=7.(38)IRLBSN−2=∑uv∈EBSN−2lndu−lndv=∑uv∈E1BSN−20+∑uv∈E2BSN−2ln3−ln4=38868146228850391125899906842624.(39)IRLUBSN−2=∑uv∈EBSN−2du−dvmindu,dv=∑uv∈E1BSN−20+∑uv∈E2BSN−23−4min3,4=4.(40)IRLFBSN−2=∑uv∈EBSN−2du−dvdu×dv=∑uv∈E1BSN−20+∑uv∈E2BSN−23−43×4=23.(41)IRLABSN−2=∑uv∈EBSN−22du−dvdu+dv=∑uv∈E1BSN−20+∑uv∈E2BSN−223−43+4=247.(42)IRD1BSN−2=∑uv∈EBSN−2ln1+du−dv=∑uv∈E1BSN−20+∑uv∈E2BSN−2ln1+3−4=187299443044960772251799813685248.(43)IRGABSN−2=∑uv∈EBSN−2lndu+dv2du×dv=∑uv∈E1BSN−20+∑uv∈E2BSN−2ln3+423×4=222866433990926718014398509481984.


## 2.2. Results for Hierarchical Hypercube NetworkHHC

Hierarchical hypercube networkHHC has many features, for example, symmetry and logarithmic diameter, which imply easy and fast algorithms for communication [55]. The structure of an n-HHC consists of three levels of hierarchy. At the lowest level of hierarchy, there is a pool of 2n nodes. These nodes are grouped into clusters of 2m nodes each, and the nodes in each cluster are interconnected to form an m−cube called the son cube or the S-cube. The set of the S-cubes constitutes the second level of hierarchy [56].Due to the hierarchical structure,HHC has the advantages that are gained by hierarchy. “In addition, hierarchical structures are capable of exploiting the locality of reference (communication), and they are fault tolerant. Other attractive properties of the HHC structure are logarithmic diameter and a topology inherited from, and closely related to, the hypercube topology. The former property implies fast communication, and the latter implies easy mapping of operations from HC to HHC. The HHC can emulate the hypercube for a large class of problems (divide conquer), without a significant increase in processing time. The HHC can embed rings and HHCs of lower dimension. In addition, HHC embeds the cube connected cycles CCC [57].” As a result, the performance of HHC is in the worst case equivalent to the performance of the CCC.The number of vertices and edges inHHC−1 are 16a+16 and 24a+20, respectively. The number of vertices and edges in HHC−2 are 16a+16 and 32a+28, respectively. HHC−1 and HHC−2 are shown in Figures 3 and 4, respectively.Figure 3
HHC
−
1
1
×
1.Figure 4
HHC
−
2
1
×
1.Theorem 3.
For the hierarchical hypercube networkHHC−1, we have(1)
VARHHC−1=2a+1/4a+12(2)
ALHHC−1=16(3)
IR1HHC−1=202a+1/a+1(4)
IR2HHC−1=2318a+11/24a+20−6a+5/2a+1(5)
IRFHHC−1=16(6)
IRFWHHC−1=4/54a+33(7)
IRAHHC−1=1213215869760357/4503599627370496(8)
IRBHHC−1=909911902320267/562949953421312(9)
IRCHHC−1=72a+166+12/24a+20−48a+40/16a+16(10)
IRDIFHHC−1=40/3(11)
IRLHHC−1=3652105019575333/562949953421312(12)
IRLUHHC−1=8(13)
IRLFHHC−1=86/3(14)
IRLAHHC−1=32/5(15)
IRD1HHC−1=6243314768165359/562949953421312(16)
IRGAHHC−1=2941534708959071/9007199254740992Proof.
The order of graph isn=VHHC−1=16a+16, and its size is m=EHHC−1=24a+20. The vertex set of HHC−1 can be divided into the following classes by means of degrees:(44)V1HHC−1=v∈VHHC−1:du=2,V2HHC−1=v∈VHHC−1:du=3.
The edge set ofHHC−1 can be divided into the following classes with respect to the degrees of end vertices:(45)E1HHC−1=uv∈EHHC−1:du=dv=3,E2HHC−1=uv∈EHHC−1:du=2,dv=3.
And the cardinality of edges is as follows:(46)E1HHC−1=24a+4,E2HHC−1=16.
First, we find some topological indices, which will be used in irregularity indices:(47)M1HHC−1=144a+104,M2HHC−1=216a+132,FHHC−1=432a+280,RRHHC−1=72a+166+12.
Now from definitions, we have(48)VARHHC−1=M1HHC−1n−2mn2=144a+10416a+16−224a+2016a+162=2a+14a+12.(49)ALHHC−1=∑uv∈EHHC−1du−dv=∑uv∈E1HHC−10+∑uv∈E2HHC−12−3=16.(50)IR1HHC−1=FHHC−1−2mnM1HHC−1=432a+280−224a+2016a+16144a+104=202a+1a+1.(51)IR2HHC−1=M2HHC−1m−2mn=216a+13224a+20−224a+2016a+16=2318a+1124a+20−6a+52a+1.(52)IRFHHC−1=FHHC−1−2M2HHC−1=432a+280−2216a+132=16.(53)IRFWHHC−1=IRFHHC−1M2HHC−1=16216a+132=16.(54)IRAHHC−1=∑uv∈EHHC−1du−1/2−dv−1/22=∑uv∈E1HHC−10+∑uv∈E2HHC−12−1/2−3−1/22=12132158697603574503599627370496.(55)IRCHHC−1=RRHHC−1m−2mn=72a+166+1224a+20−224a+2016a+16=72a+166+1224a+20−48a+4016a+16.(56)IRDIFHHC−1=∑uv∈EHHC−1dudv−dvdu=∑uv∈E1HHC−10+∑uv∈E2HHC−123−32=403.(57)IRLHHC−1=∑uv∈EHHC−1lndu−lndv=∑uv∈E1HHC−10+∑uv∈E2HHC−1ln2−ln3=3652105019575333562949953421312.(58)IRLUHHC−1=∑uv∈EHHC−1du−dvmindu,dv=∑uv∈E1HHC−10+∑uv∈E2HHC−12−3min2,3=8.(59)IRLFHHC−1=∑uv∈EHHC−1du−dvdu×dv=∑uv∈E1HHC−10+∑uv∈E2HHC−12−32×3=863.(60)IRLAHHC−1=∑uv∈EHHC−12du−dvdu+dv=∑uv∈E1HHC−10+∑uv∈E2HHC−122−32+3=325.(61)IRD1HHC−1=∑uv∈EHHC−1ln1+du−dv=∑uv∈E1HHC−10+∑uv∈E2HHC−1ln1+2−3=6243314768165359562949953421312.(62)IRGAHHC−1=∑uv∈EHHC−1lndu+dv2du×dv=∑uv∈E1HHC−10+∑uv∈E2HHC−1ln2+322×3=29415347089590719007199254740992.Theorem 4.
For the hierarchical hypercube networkHHC−2, we have(1)
VARHHC−2=2a+1/4a+12(2)
ALHHC−2=24(3)
IR1HHC−2=282a+1/a+1(4)
IR2HHC−2=4216a+11/32a+28−8a+7/2a+1(5)
IRFHHC−2=24(6)
IRFWHHC−2=3/64a+44(7)
IRAHHC−2=20694009944167803/144115188075855872(8)
IRBHHC−2=15520507458125877/9007199254740992(9)
IRCHHC−2=128a+483+16/32a+28−64a+56/16a+16(10)
IRDIFHHC−2=14(11)
IRLHHC−2=3886814622885039/562949953421312(12)
IRLUHHC−2=8(13)
IRLFHHC−2=43(14)
IRLAHHC−2=48/7(15)
IRD1HHC−2=18729944304496077/1125899906842624(16)
IRGAHHC−2=2228664339909267/9007199254740992Proof.
The order of graph isn=VHHC−2=16a+16, and its size is m=EHHC−2=32a+28. The vertex set of HHC−2 can be divided into the following classes by means of degrees:(63)V1HHC−2=v∈VHHC−2:du=3,V2HHC−2=v∈VHHC−2:du=4.
The edge set ofHHC−2 can be divided into the following classes with respect to the degrees of end vertices:(64)E1HHC−2=uv∈EHHC−2:du=dv=4,E2HHC−2=uv∈EHHC−2:du=3,dv=4.
And the cardinality of edges is as follows:(65)E1HHC−2=32a+4,E2HHC−2=24.
First, we find some topological indices, which will be used in irregularity indices:(66)M1HHC−2=256a+200,M2HHC−2=512a+352,FHHC−2=1024a+728,RRHHC−2=128a+483+16.
Now, from definitions, we have(67)VARHHC−2=M1HHC−2n−2mn2=256a+20016a+16−232a+2816a+162=2a+14a+12.(68)ALHHC−2=∑uv∈EHHC−2du−dv=∑uv∈E1HHC−20+∑uv∈E2HHC−23−4=24.(69)IR1HHC−2=FHHC−2−2mnM1HHC−2=1024a+728−232a+2816a+16256a+200=282a+1a+1.(70)IR2HHC−2=M2HHC−2m−2mn=512a+35232a+28−232a+2816a+16=4216a+1132a+28−8a+72a+1.(71)IRFHHC−2=FHHC−2−2M2HHC−2=1024a+728−2512a+352=24.(72)IRFWHHC−2=IRFHHC−2M2HHC−2=24512a+352=24.(73)IRAHHC−2=∑uv∈EHHC−2du−1/2−dv−1/22=∑uv∈E1HHC−20+∑uv∈E2HHC−23−1/2−4−1/22=20694009944167803144115188075855872.(74)IRBHHC−2=∑uv∈EHHC−2du1/2−dv1/22=∑uv∈E1HHC−20+∑uv∈E2HHC−231/2−41/22=155205074581258779007199254740992.(75)IRCHHC−2=RRHHC−2m−2mn=128a+483+1632a+28−232a+2816a+16=128a+483+1632a+28−64a+5616a+16.(76)IRDIFHHC−2=∑uv∈EHHC−2dudv−dvdu=∑uv∈E1HHC−20+∑uv∈E2HHC−234−43=14.(77)IRLHHC−2=∑uv∈EHHC−2lndu−lndv=∑uv∈E1HHC−20+∑uv∈E2HHC−2ln3−ln4=3886814622885039562949953421312.(78)IRLUHHC−2=∑uv∈EHHC−2du−dvmindu,dv=∑uv∈E1HHC−20+∑uv∈E2HHC−23−4min3,4=8.(79)IRLFHHC−2=∑uv∈EHHC−2du−dvdu×dv=∑uv∈E1HHC−20+∑uv∈E2HHC−23−43×4=43.(80)IRLAHHC−2=∑uv∈EHHC−22du−dvdu+dv=∑uv∈E1HHC−20+∑uv∈E2HHC−223−43+4=487.(81)IRD1HHC−2=∑uv∈EHHC−2ln1+du−dv=∑uv∈E1HHC−20+∑uv∈E2HHC−2ln1+3−4=187299443044960771125899906842624.(82)IRGAHHC−2=∑uv∈EHHC−2lndu+dv2du×dv=∑uv∈E1HHC−20+∑uv∈E2HHC−2ln3+423×4=22286643399092679007199254740992.


## 3. Conclusion

In this paper, we have computed several degree-based irregularity indices of block shift networks and hierarchical hypercube networks. Our results are applicable in chemistry, physics, and other applied sciences. Topological indices help us to understand structural properties of understudy networks [58–63]. The computed results give understanding about the irregularities of understudy networks.



---

*Source: 1042308-2019-12-18.xml*