On Some Ev-Degree and Ve-Degree Dependent Indices of Benes Network and Its Derived Classes

1  Introduction

A classic and helpful strategy is to attach various graphs to objects that may be an algebraic structure, a chemical structure of a drug, or a network, which assists in understanding certain features of the objects. Various graph parameters can be associated with the properties of the structure under examination which leads to a deeper study of its theory. These properties may include the algebraic properties of the zero divisor graphs and the physio chemical properties of the chemical structures. By adopting this strategy, several researchers studied different objects such as algebraic objects [1], pysio-chemical properties of chemical structures [2–4], drugs used for breast cancer treatment [5], and interconnection networks [6]. The analysis of networks, such as Butterfly network [7], Benes network [8,9], Interconnection network [6,10] and David-derived network [11] through similar approach, is one of the most recent developments in the field of graph theory.

The class of topological indices (TIs) is a significant class of parameters associated with graphs. Many TIs have been introduced and studied during the last fifty years. Among the class of degree dependent TIs, the Zagreb indices (ZIs) introduced in [12], vastly studied due to the ability to estimate the π-electron energy is still a topic of interest [13] after 5 decades. Another degree dependent graph parameter, used in mathematical chemistry is known as Randíc index (RI). The details regarding its applications and its different variants are presented in [14]. Furthermore, the geometric-arithmetic (GA) index was formulated [15] in an attempt to exceed the Randíc index in terms of predicting ability. Its chemical use and mathematical characteristics drew scientists to examine it further in [16]. Another significant index, known as Atom bond connectivity index (ABC-index) was put forward by Estrada and was used for investigating stain energy and stability of cycloalkanes and linear alkanes, see [17–20]. Another graph invariant, having connections with eigen values of graphs was introduced in [21] and is a topic of interest till now known as Harmonic index (HI). In [22], Chellali et al. introduced some new degrees of a vertex in a graph, known as ve-degree and ev-degree. Mathematical notions related to these degrees were also studied by Horoldagva et al. [23]. The ZIs and RI, based on ev-degree and ve-degree notions, are formulated in [24–27] and it was analyzed that predicting ability of ve-degree ZI has improved as compared to its classical version. For more developments on the study of TIs, see [28–32].

Butterfly graphs are the associated graphs of Fast Fourier Transforms (FFT) networks which are especially effective in performing the FFT. The butterfly network is constructed by a sequence of switch stages and connector patterns that allow ′n′ different configurations. The ′n′ outputs should be connected to ′n′ inputs. Furthermore, the Benes network obtained by attaching back-to-back butterfly networks is known for permutation routing [8]. These networks are key multistage interconnection networks with appealing communication network topologies [9]. The graph associated to s-dimensional butterfly network consists of vertex set V with elements [v, i] in which v is an s-bit binary number representing the row of the node and 0≤i≤s. The edge between any two vertices [v, i] and [v′, i′] exists if and only if i′=i+1 and either (1) v=v′ or (2) v, v′ differ in exactly the ith bit. Clearly, for |V(BF(s))|=2s(s+1) and |E(BF(s))|=s2s+1. Further, an s dimensional Benes network is obtained by connecting back-to-back butterflies BF(s). An s-dimensional Benes network is denoted by B(s), for example B(3) is shown in Fig. 1. Further, |V(B(s))|=2s(2s+1) and |E(B(s))|=s2s+2. For more regarding the structure and construction of butterfly and benes networks, we refer readers to [6]. By keeping in view the importance of these networks, Hussain et al. recently introduced some families of graphs obtained by Horizontal and vertical identifications of Benes network. These new graphs are known as Horizontal Cylindrical (HCB(s)) and Vertical Cylindrical (VCB(s)) Benes network. In these networks, |V(HCB(s))|=(2s−1)(2s+1), |V(VCB(s))|=2s+1s, |E(HCB(s))|=2s(2s+1−1) and |E(VCB(s))|=2s+2s. For the complete details regarding the structures HCB(s) and VCB(s), see Figs. 2 and 3 [33,34].

Figure 1: 3-dimentional Benes network

Figure 2: Normal representation of VCB(3)

Figure 3: Normal representation of HCB(3)

2  Preliminaries

Let G(V,E) denotes a connected graph having V as a vertex set and E as an edge set. For u∈V, the degree u, denoted by d(u) is the cardinality of edges incident to it. For any u,v∈V, the vertices u, v are called adjacent if there is e∈E with e=uv. For u∈V its open neighborhood, denoted by N(u), is defined as: N(u)={v∈V:thereexistse∈Ewithe=uv} and the closed neighborhood N[u]={u}∪N(u). For uv=e∈E, its ev-degree is the cardinality of the vertices in N[u]∪N[v] and the ve-degree of v∈V is the cardinality of N[v]. The ev-degree of e and ve-degree of u are denoted by dev(e) and dve(u), respectively. In Table 1, we include the formulae of ev-degree and ve-degree dependent variants of the well known TIs discussed above.

3  Ev-Degree Dependent Topological Indices for Bensen Networks and Its Derived Classes

In this section, we prove analytical formulae for the ev-degree dependent TIs for B(s), VCB(s) and HCB(s). The formulae have been established through partition of the vertex sets of B(s), VCB(s) and HCB(s) on the basis of ev-degree as shown in Tables 2–4. We start with the following theorem for B(s).

Theorem 3.1. For an s-dimensional Benes network B(s), we have:

(i) Mev(B(s))=2s+2(64s−28).

(ii) Rev(B(s))=2s+2(16+s8−1).

Proof.

By using Table 2, we compute the ev-degree based indices for Benes network as follows:

(i)

Mev(B(s))=∑e∈E(B(s))dev(e)2=(6)2(2s+2)+(8)2(s)2s+2−2s+2=2s+2(64s−28).

(ii)

Rev(B(s))=∑e∈E(B(s))dev(e)−12=(6)−12(2s+2)+(8)−12(s)2s+2−2s+2=2s+2(16+s8−1).

Now, we continue to prove the ev-degree dependent TIs for VCB(s) in the next theorem.

Theorem 3.2. For VCB(s), the Mev(VCB(s)) and Rev(VCB(s)) are given as:

(i) Mev(VCB(s))=2s+9⋅s.

(ii) Rev(VCB(s))=2s+32⋅s.

Proof. (i) From Table 3 and the definition of Mev, we have:

Mev(VCB(s))=∑e∈E(VCB(s))dev(e)2=(8)2(2)(s)(2s+2)=2s+9s.

(ii) From Table 3 and the definition of Rev, we have:

Rev(VCB(s))=∑e∈E(VCB(s))dev(e)−12=(8)−12(2)(r)(2s+2)=2s+32⋅s.

We conclude the results of this section by proving the ev-degree dependent TIs for HCB(s):

Theorem 3.3. For HCB(s), the Mev(HCB(s)) and Rev(HCB(s)) are given as:

(i) Mev(HCB(s))=2s+7(2s−1)+320s−138.

(ii) Rev(HCB(s))=162s+2+s2s[6+245+6+2]+47+22−126−810+23+62.

Proof. (i) From Table 4 and the definition of Mev, we have:

Mev(HCB(s))=∑e∈E(HCB(r))dev(e)2=(6)2(2r+2−12)+(7)2(4)+(8)2(4)+(8)2(4)(s−1)(ss−3)+(9)2(2)+(10)2(8)(s−1)+(12)2(2)(s−1)=2s+7+2s(256s−256)+320s−138,

which upon simplification gives the required result.

(ii) From Table 4 and the definition of Rev, we have:

Rev(HCB(s))=∑e∈E(HCB(r))dev(e)−12=(6)−1/2(2r+2−12)+(7)−1/2(4)+(8)−1/2(4)+(8)−1/2(4)(s−1)(ss−3)+(9)−1/2(2)+(10)−1/2(8)(s−1)+(12)−1/2(2)(s−1)=162r+2+22s2s+1282s[48+810+13]s+47+22−126−810+23+62,

which upon simplification gives the required result.

Now, we present an example of the results proved in this section:

Example 3.1. By taking s=4 in Theorem 3.1, Theorem 3.2 and Theorem 3.3, we obtain the values of ev-degree based TIs for B(4), VCB(4) and HCB(4) as shown in Table 5:

4  Ve-Degree Dependent Topological Indices for Bensen Networks and Its Derived Classes

In this section, we develop formulae for the ve-degree dependent TIs for B(s), VCB(s) and HCB(s). The key to obtaining these formulae is to obtain partition the edge set of B(s), VCB(s) and HCB(s) on the basis of ve-degrees of the end vertices of each edge as shown in Tables 6–8.

Theorem 4.1. For B(s), the ve-degree dependent TIs M1αve(B(s)), M1βve(B(s)), M2ve(B(s)), Rve(B(s)), ABCve(B(s)), GAve(B(s)), Hve(B(s)) and χve(B(s)) are given as:

(i) M1αve(B(s))=32.2s(16s−11).

(ii) M1βve(B(s))=2s+2(32s−16).

(iii) M2ve(B(s))=2s+2(256s−224).

(iv) Rve(B(s))=2s+2[196+1192+s16−18].

(v) ABCve(B(s))=2s+2[296+7192+2s4−22].

(vi) GAve(B(s))=2s+2[265+8314+s−2].

(vii) Hve(B(s))=2s+2[13280+s16].

(viii) χve(B(s))=2s+2[125+s814+122].

Proof. (i) From Table 6 and the definition of M1αve, we have:

M1αve(B(s))=∑v∈V(B(s))dve(v)2=(8)22s+1+(12)22s+1+(16)2(2s−3)2s=2s+1(208)+512s2s−7682s,

which upon simplification gives the required formula.

(ii) The Table 6 and the formula for M1βve yields:

M1βve(B(s))=∑uv∈E(B(s))(dve(u)+dve(v))=(12+8)2s+2+(12+16)2s+2+(16+16)(s2s+2−2s+3)=2s+2(32s−16).

(iii) The Table 6 and the formula for M2ve yields:

M2ve(B(s))=∑uv∈E(B(s))(dve(u)dve(v))=(12)(8)2s+2+(12)(16)2s+2+(16)(16)(s2s+2−2s+3)=2s+2(256s−224).

(iv) The Table 6 and the formula for Rve gives:

Rve(B(s))=∑uv∈E(B(s))((dve(u)dve(v)))−1/2=((12)(8))−1/22s+2+((12)(16))−1/22s+2+((16)(16))−1/2(s2s+2−2s+3)=2s+2[196+1192+s16−18].

(v) The Table 6 and the formula for ABCve yields:

ABCve(B(s))=∑uv∈E(B(s))dve(u)+dve(v)−2dve(u)dve(v)=12+8−2(12)(8)2s+2+12+16−2(12)(16)2s+2+16+16−2(16)(16)(s2s+2−2s+3)=2s+2[296+7192+2s4−22].

(vi) The Table 6 and the formula for GAve yields:

GAve(B(s))=∑uv∈E(B(s))2dve(u)dve(v)dve(u)+dve(v)=2(12)(8)12+82s+2+2(12)(16)12+162s+2+2(16)(16)16+16(s2s+2−2s+3)=2s+2[265+8314+s−2].

(vii) The Table 6 and the formula for Hve yields:

Hve(B(s))=∑uv∈E(B(s))2dve(u)+dve(v)=212+82s+2+212+162s+2+216+16(s2s+2−2s+3)=2s+2[13280+s16].

(viii) Lastly, the Table 6 and the formula for χve gives:

χve(B(s))=∑uv∈E(B(s))(dve(u)+dve(v))−1/2=(12+8)−1/22s+2+(12+16)−1/22s+2+(16+16)−1/2(s2s+2−2s+3)=2s+2[125+127s42+122],

which upon simplification gives the required formula.

By using the Table 7 and the formulae of TIs defined in Table 1, we get the following results for the VCB(s).

Theorem 4.2. For VCB(s), ve-degree dependent TIs M1αve(B(s)), M1βve(B(s)), M2ve(B(s)), Rve(B(s)), ABCve(B(s)), GAve(B(s)), Hve(B(s)) and χve(B(s)) are given as:

(i) M1αve(VCB(s))=256s2s+1.

(ii) M1βve(VCB(s))=32s2s+2.

(iii) M2ve(VCB(s))=256s2s+2.

(iv) Rve(VCB(s))=s162s+2.

(v) ABCve(VCB(s))=2s42s+2.

(vi) GAve(VCB(s))=s2s+2.

(vii) Hve(VCB(s))=s162s+2.

(viii) χve(VCB(s))=s422s+2.

By using the Table 8 and the formulae of TIs defined in Table 1, we get the following results for the HCB(s).

Theorem 4.3. For HCB(s), the ve-degree dependent TIs M1αve(B(s)), M1βve(B(s)), M2ve(B(s)) and Rve(B(s)) are given as:

(i) M1αve(HCB(s))=2s(512s−352)+816s.

(ii) M1βve(HCB(s))=(16s+409)2s+3+128s−88.

(iii) M2ve(HCB(s))=(8s−7)2s+7+3040s−2932.

(iv) Rve(HCB(s))=[s8+23+6−32122]2s+1+[223−4728]s+6210+4130+27−56+113+114+436−423+321−4717+272+1421+135+4314−15456.

(v) ABCve(HCB(s))=[32s16+56+723−2]2s+1+[4173−7324+147+446314]s+631210+423130+2227+1056+2913+3014+43036−5683+8173−7322+33+231414+24272+2337221+4335−104634.

(vi) GAve(HCB(s))=[s+265+437−2]2s+1+[828817+450423+2826−14]s+1221031+813023+411211+420829+222415+421615−3228834+437+239221+433637+353−1050423−46−83+30.

(vii) Hve(HCB(s))=63522s+3[s8−14]−788521436s−17.57077354.

(viii) χve(HCB(s))=[s22+15+17−12]2s+1+[s22+1634+114+84]s+631+822−25+429+1230−107−3234−214+12+437+13−2046+27+72.

Now, we conclude the section by including the following example:

Example 4.1. By taking s=4 in Theorem 4.1, Theorem 4.2 and Theorem 4.3, we obtain the values of ve-degree based TIs for B(4), VCB(4) and HCB(4) as shown in Table 9:

5  Graphical Analysis

We proceed further with our obtained formulae in previous section to study graphical patterns in the values of TIs of B(s), HCB(s) and HCB(s). In Figs. 4–6, the patterns of ZI(VE), RI(VE), ABC-I(VE), GA-(VE) and HI(VE) (on y-axis), where the value of s has been taken on x-axis, for B(s), HCB(s) and VCB(s) have been presented. All the figures show the rapid rise in the values of each TI for B(s), HCB(s) and HCB(s) with the rise in the value of s. The trends in Fig. 4 (L) show that the HCB(s) attains higher values of ZI(VE), whereas values of ZI(VE) for VCB(s) remain between B(s) and HCB(s). Similar trend for RI(VE) has been shown in Fig. 4 (R). In Fig. 5 (L), it can be seen that the values of ABC-I(VE) show different behaviours as in case of ZI(VE) and RI(VE). The ABC-I(VE) attains lowest values for HCB(s), whereas values for B(s) remain between VCB(s) and HCB(s). Furthermore, the trend for HI(EV) is shown in Fig. 5 (R). In the case of GA(VE), the values for B(s) remain the highest and the values for VCB(s) remain between the values of B(s) and HCB(s), see Fig. 6.

Figure 4: Graphical comparison between ZI(VE) on left (L) and RI(VE) on right (R) of B(s), HCB(s) and HCB(s)

Figure 5: Graphical comparison between ABC(VE) on left (L) and HI(VE) on right (R) of B(s), HCB(s) and HCB(s)

Figure 6: Graphical comparison between GA-I(VE) of B(s), HCB(s) and HCB(s)

6  Conclusion

The study of newly formed networks is always a fascinating topic. Using B(s), several novel networks such as HCB(s) and VCB(s) have been defined through identifications in [33] and further investigated in [34]. Furthermore, the ev-degree and the ve-degree of these structures were not investigated yet. In the current work, we constructed the ev-degree based partition of the vertex set and the ve-degree based partition of the edge set for these networks. Through these partitions, we developed formulae for several ev-degree and ve-degree based TIs for B(s), HCB(s) and VCB(s) in terms of the parameter s. Further, we presented the comparative analysis of the values of ZI(VE), RI(VE), ABC-I(VE), GA-I(VE) and HI(VE) for B(s), HCB(s) and VCB(s). It is observed that similar patterns have been developed for ZI(VE) and RI(VE), whereas the other three TIs produce different trends.

Acknowledgement: The authors are thankful to their respective institutes.

Funding Statement: This work is partially supported by the National Natural Science Foundation of China (Grant No. 61702291); China Henan International Joint Laboratory for Multidimensional Topology and Carcinogenic Characteristics Analysis of Atmospheric Particulate Matter PM2.5.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.