# COMPUTING TOPOLOGICAL INDICES OF DIRECT INTERCONNECTION NETWORKS.

Byline: Fatima Zulfiqar and Sakander HayatAbstract

A direct interconnection network (IN) of a multiprocessor system is represented by a connected graph whose vertices represent processing nodes and edges represent communication links. A processing node (PN) usually consists of one or more processors local memory and communication router.

The butterfly and Benes networks are important class of multistage direct interconnection networks which are defined based on the schemes that connect the units of a multiprocessing system and needs n stages to connect 2n processors; at each stage a switch is thrown depending on a particular bit in the addresses of the processors being connected. In this paper degree based topological indices of these direct interconnection networks are strong-minded.

Keywords: General sum-connectivity index Harmonic index Zagreb index Atom-bond connectivity index Geometric arithmetic index Butterfly network Benes network

1 INTRODUCTION AND PRELIMINARY RESULTS

A single number which characterizes the graph of a molecular structure is called a graph-theoretical invariant or topological index. Topological indices have been found as a base to understand the topologies of interconnection networks. In addition these numerical parameters discuss the structural properties of these important architectures.

A direct interconnection network (IN) of a multiprocessor system is represented by a connected graph whose vertices represent processing nodes and edges represent communication links. A processing node (PN) usually consists of one or more processors local memory and communication router. An IN should transfer a maximum number of messages in the shortest time with minimum cost and maximal reliability. Clearly any design of an IN is a tradeoff of various contradictory requirements.

Butterfly graphs are defined as the underlying graphs of Fast Fourier Transforms (FFT) networks which can perform the FFT very efficiently. The butterfly network consists of a series of switch stages and interconnection patterns which allows n ' inputs to be connected to n ' outputs. The Benes network consists of back-to-back butterflies. As butterfly is known for FFT Benes is known for permutation routing [2]. The butterfly and Benes networks are important multistage interconnection networks which possess attractive topologies for communication networks [17]. They have been used in parallel computing systems such as IBM SP 1 /SP 2 MIT Transit Project NEC Cenju- 3 and used as well in the internal structures of optical couplers [16 19].

The multistage networks have long been used as communication networks for parallel computing [15]. A graph G(V E) with vertex set V and edge set E is connected if there exist a connection between any pair of vertices in G . The degree of a vertex in a network graph is the number of vertices which are connected to that fixed vertex by the edges.

In this article G is considered to be a connected graph with vertex set V (G) and edge set E(G) du is the degree of vertex u V (G) . The notations used in this article are mainly taken from books [4 10].

The general Randi c index was proposed by Bollobas and ErdAls [3] and Amic et al. [1] independently in 1998 . Then it has been extensively studied by both mathematicians and theoretical chemists [13]. Definition 1.1. For a graph G the general Randi c index R (G) is the sum of (du dv ) over all edges e = uv E(G) defined as Equation

where ( 0) is an arbitrary real number.

With motivation from the Randi c index a closely related variant of the Randi c connectivity index called the sum- connectivity index was recently proposed by Zhou and Trinajsti c [20] in 2009.

Definition 1.2. The sum- connectivity index G is defined as follows: Equation

and the general sum-connectivity index Equation

X(G) is a graph-based molecular structure descriptor. The sum-connectivity index has been found to correlate well with -electronic energy of benzenoid hydrocarbons. The the sum-connectivity index and original Randi c connectivity index are highly intercorrelated molecular descriptors. Some mathematical properties of the sum-connectivity and general sum-connectivity are given in [5 6].

An important topological index introduced about forty years ago by Ivan Gutman and Trinajsti c is the Zagreb index or more precisely first zagreb index denoted by M1 (G) and was defined as the sum of degrees of end vertices of all edges of G . Definition 1.3. The first zagreb index is defined as Equation

One of the well-known connectivity topological index is atom-bond connectivity ( ABC ) index introduced by Estrada et al. in [7].

Definition 1.4. For a graph G the ABC index is defined as Equation

Another well-known connectivity topological descriptor is geometric-arithmetic (GA) index which was introduced by Vuki c evi c et al. in [18].

Definition 1.5. Consider a graph G then its GA index is defined as Equation

The fourth version of ABC index is introduced by Ghorbani et al. [8] recently in 2010. Definition 1.6. Let G be a graph then its fourth ABC index is defined as Equation

Recently fifth version of GA index is proposed by Graovac et al. [9] in 2011. Definition 1.7. For a graph G the fifth version of GA index is defined as Equation

Following lemma is important throughout our discussion.

Lemma 1.1. [12] For any graph G when = 1 H (G) = 2 X1 (G).

Closed formulas of these indices for two important classes of interconnection networks named as butterfly and Benes networks. For further study of topological indices of networks see [11 14].

2.1 Results for butterfly network

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The set V of vertices of an r -dimensional butterfly network correspond to pairs [w i] where i is the dimension or level of a node (0 i r) and w is an r -bit binary number that denotes the row of the node. Two nodes [w i] and [w i] are linked by an edge if and only if i = i 1 and either:

1. w and w are identical or

2. w and w differ in precisely the i th bit.

The edges in the network are undirected. An r -dimensional butterfly network is denoted by BF (r) . Manuel et el. [17] proposed the diamond representations of these networks. The normal and diamond representations of 3 -dimensional butterfly network are given in Fig. 1. The vertex and edge cardinalities are 2r (r 1) and r 2r 1 respectively.

Equations

Now we compute certain degree based topological indices for butterfly network. Following theorem presents the analytically closed formula of general sum-connectivity index Equation for this network.

Theorem 2.1.1. Consider the butterfly network then its general sum-connectivity index is equal to Equation

Harmonic First Zagreb ABC4 and GA5 indices and give Proof. Consider H be the butterfly network with defining parameter r . The number of vertices and edges in H are 2r (r 1) and r 2r 1 respectively.

There are two types of edges in H based on degrees of end vertices of each edge. Table 1 shows such an edge partition of H .

Table 1: Edge partition of butterfly network BF (r) based on degrees of end vertices of each edge.

(d u d v )###where###(24)###(44)

uv E (G)

Number of edges###2r 2###2r 1 (r 2)

Equations

The ABC and GA indices of this network have already been studied in other papers. We compute ABC4 and GA5 indices of this r -dimensional network. We need an edge partition of this graph based on degree sum of neighbors of end vertices of each edge. Table 2 shows such a partition of this graph.

Table 2: Edge partition of graph of r -dimensional

( S S ) where###Number of edges

u###v

uv E (G)

(812)###2r 2

(1216)###2r 2

(1616)###(r 4)2r 1

utterfly network based on degree sum of vertices lying at unit distance from end vertices of each edge.

Following theorem exhibits the analytically closed result of ABC4 index for this network. Theorem 2.1.2. Consider the r -dimensional butterfly network then its ABC4 index is a non-linear expression in parameter r Equation

Proof. Consider H be the r -dimensional butterfly network with defining parameter r . The number of vertices and edges in H are 2r (r 1) and r 2r 1 respectively. There are three types of edges in H based on degrees of end vertices of each edge. Table 2 shows such an edge partition of H . We know Equation

In the following theorem we compute GA5 index of r - dimensional butterfly network.

Theorem 2.1.3. Consider the r -dimensional butterfly network the its GA5 index is a non-linear expression in parameter r Equation

Proof. Let H be the r -dimensional butterfly network. We easily prove it by using edge partition given in table 2. We know Equation

Now we deal with another type of important direct IN named as Benes network. We give analytically closed results for topological indices of these networks which provide us a base to understand their topologies of these well-designed architectures.

2.2 Results for Benes network

Back butterflies. An r -dimensional Benes network has 2r 1 levels each level with 2r nodes. The level 0 to level r nodes in the network form an r -dimensional butterfly. The middle level of the Benes network is shared by these butterflies. An r -dimensional Benes is denoted by B(r) . Manuel et al. proposed the diamond representation of the Benes network also [17]. Fig. 2 shows the normal representation of B(3) network while diamond representation of B(3) is depicted in Fig. 3. The number of vertices and number of edges in an r -dimensional Benes network are 2r (2r 1) and r 2 r 2 respectively.

Now we compute certain degree based topological indices for Benes network. Following theorem presents the analytically closed formula of general sum-connectivity index Equation

Theorem 2.2.1. Consider the Benes network B(r) then its general sum-connectivity index is equal to Equation

Proof. Consider H be the Benes network with defining parameter r . The number of vertices and edges in H are 2r (2r 1) and r 2r 2 respectively. There are two types of edges in H based on degrees of end vertices of each edge. Table 3 shows such an edge partition of H.

Table 3: Edge partition of Benes network B(r) based on degrees of end vertices of each edge

(du d v ) where###(24)###(44)

uv E (G)

Number of edges###2r2###2r2###(r 1)

Equations

The ABC and GA indices of this network have already been calculated in other papers. We compute ABC4 and GA5 indices of this r -dimensional network. We need an edge partition of this graph based on degree sum of neighbors of end vertices of each edge. Table 4 shows such a partition of this graph.

Table 4: Edge partition of graph of r -dimensional Benes network based on degree sum of vertices lying at unit distance from end vertices of each edge.

( Su S v )###where Number of edges

uv E (G)

###r 2

###(812)###2

###(1216)###2r 2

###(1616)###(r 2)2r 2

Following theorem exhibits the analytically closed result of ABC4 index for this network.

Theorem 2.2.2. Consider the r -dimensional Benes network then its ABC4 index is a non-linear expression in parameter r Equation

3 CONCLUDING REMARKS

In this paper certain degree based topological indices namely general sum-connectivity index Harmonic index first Zagreb index fourth atomic-bond connectivity index ( ABC4 ) and fifth geometric-arithmetic index ( GA5 ) for two important class of networks were studied for the first time. We computed analytically closed results of these degree based topological indices for butterfly and Benes interconnection networks. These results provide a base to understand the topology of these networks. In future we are interested to study fat tree network and extended fat tree network.

REFERENCES

1. D. Amic D. Beslo B. Lucic S. Nikolic N. Trinajsti c The vertex-connectivity index revisited J. Chem. Inf. Comput. Sci. 38(1998) 819 822 .

2. V. E. Benes Mathematical theory of connecting networks and telephone traffic Academic Press (1965) .

3. B. Bollobas P. ErdAls Graphs of extremal weights Ars Combinatoria 50(1998) 225 233 .

4. M. V. Diudea I. Gutman J. Lorentz Molecular Topology Nova Huntington 2001.

5. Z. Du B. Zhou N. Trinajsti'c A note on generalized sum- connectivity index Appl. Math. Lett. 24(2010) 402 - 405 .

6. Z. Du B. Zhou N. Trinajsti'c Minimum sum-connectivity indices of trees and unicyclic graphs of a given matching number J. Math. Chem. 47(2010) 842 - 855 .

7. E. Estrada L. Torres L. Rodriguez I. Gutman An atombond connectivity index: Modelling the enthalpy of formation of alkanes Indian J. Chem. 37 A(1998) 849 855 .

8. M. Ghorbani M. A. Hosseinzadeh Computing ABC4 index of nanostar dendrimers Optoelectron. Adv. Mater. Rapid Commun. 4(2010) 1419 1422 .

9. A. Graovac M. Ghorbani M. A. Hosseinzadeh Computing fifth geometric-arithmetic index for nanostar dendrimers J. Math. Nanosci. 1(2011) 33 42 .

10. I. Gutman O. E. Polansky Mathematical concepts in organic chemistry Springer-Verlag New York 1986.

11. S. Hayat M. Imran Computation of topological indices of certain networks Appl. Math. Comput. 244(2014) 936 951.

12. Y. Hu X. Zhou On the harmonic index of the unicyclic and bicyclic graphs WSEAS Transaction on Mathematics 6(12)(2013) 716 726 .

13. Y. Hu X. LiY. Shi T. Xu I. Gutman On molecular graphs with smallest and greatest zeroth-order general Randi c index MATCH Commun. Math. Comput. Chem. 54(2005) 425 434 .

14. M. Imran S. Hayat M. Y. H. Malik On topological indices of certain interconnection networks Appl. Math. Comput. 240(2014) 213 228 .

15. S. Konstantinidou The selective extra stage butterfly IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 1(1992) 502 506 .

16. X. Liu Q. P. Gu Multicasts on WDM all-optical butterfly networks J. Inf. Sci. Eng. 18(2002) 1049 1058 .

17. P. D. Manuel M. I. Abd-El-Barr I. Rajasingh B. Rajan An efficient representation of Benes networks and its applications J. Discr. Algo. 6(2008) 1119 .

18. D. Vuki c evi c B. Furtula Topological index based on the ratios of geometrical and arithmetical means of end- vertex degrees of edges J. Math. Chem. 46(2009) 1369 1376 .

19. J. Xu Topological structure and analysis of interconnection networks Kluwer Academic Publishers (2001) .

20. B. Zhou N. Trinajsti'c On general sum-connectivity index J. Math. Chem. 47(2010) 210 218 .

Printer friendly Cite/link Email Feedback | |

Publication: | Science International |
---|---|

Article Type: | Report |

Date: | Feb 28, 2015 |

Words: | 2399 |

Previous Article: | HE TRICYCLIC GRAPHS WITH THE EXTREMUM ZEROTH-ORDERGENERAL RANDIC INDEX. |

Next Article: | EMPLOYEE PERFORMANCE FROM THE LENS OF ISLAMIC WORK ETHICS: MEDIATING ROLE OF PERSONALITY X AND Y. |

Topics: |