Restricted Arc Connectivity Of Hypercube-like Networks

The edge connectivity of a graph can be used to measure the network reliability.when an interconnection network is modeled by a simple graph.The l-restricted edge connec-tivity provides a more accurate index to measure the reliability of networks than the edge connectivity.The directed network has some incomparable advantages over the undirected network.For example,when a directed network accommodates a large number of nodes,it does not need complex communication hardware as the traditional bidirectional network.Therefore,the directed networks also have received much attention.The arc connectivity is a parameter to measure the reliability of directed networks.The super arc connected net-works(the super-λ networks)are the most reliable networks in terms of the arc connectivity.In 2007,as a measurement of super-A property,the concept of restricted arc connectivity was introduced by Volkmann.Since then,much research has been done on restricted arc connectivity in the general digraph.However,researchers know less about the restricted arc connectivity of directed interconnection networks than their undirected counterparts.The hypercube is one of the most commonly used interconnection networks for multi-processor systems because of its special structure and good properties.Some hypercube-like networks,such as folded hypercubes and k-ary n-cubes have been also proposed.Unidirec-tional hypercubes and unidirectional folded hypercubes are generalizations of hypercubes and folded hypercubes respectively.This thesis consists of four chapters.We use the restricted edge(arc)connectivity to study the reliability of k-axy n-cubes、unidirectional hypercubes and unidirectional folded hypercubes.Chapter 1 introduces the used basic concepts and notations,then we give the main concepts and research background of this thesis.Chapter 2 first studies some properties of k-ary n-cubes,then determines the 4-restricted edge connectivity of k-ary n-cubes and obtains the following:Let k ≥ 3,n ≥ 2 be two integers.The k-ary n-cubes Qnk is A4-connected and its 4-restricted edge connectivity is A4(Qnk)= 8n-8.In 2008,Wang and Lin introduced the concept of minimum arc-degree and proved that it is an upper bound on restricted arc connectivity.Chapter 3 first determines the minimum arc-degree of unidirectional hypercubes UQn,then proves that its restricted arc connectivity is equal to its minimum arc-degrees and obtains the following:The restricted arc connectivity of the unidirectional hypercube UQn is n-1 when n is even and is n-2 when n is odd.The result shows that unidirectional hypercubes are reliable in terms of the restricted arc connectivity.In addition,if there exist more arc disjoint paths between any two vertices in a directed network,then the fault tolerance of the network is higher.Motivated by this,the maximally local-arc-connectivity of directed networks was proposed.In the third section of this chapter,the arc fault tolerance of unidirectional hypercubes for maximally local-arc-connected is determined.This thesis introduces the n-dimensional unidirectional folded hypercube UFn by ori-enting every edge in the folded hypercube,which is one variant of the n-dimensional uni-directional hypercube.In Chapter 4,we first determine the minimum arc-degrees of uni-directional folded hypercubes UFn,then prove that its restricted arc connectivity is equal to its minimum arc-degrees and obtain the following:The restricted arc connectivity of the unidirectional folded hypercube UFn is n-1 when n is even and is n when n is odd.In the end,as an application of the above results,we prove that both unidirectional hypercubes and unidirectional folded hypercubes are super-λ.