The Study Of Cycles Embedding In Interconnection Networks

Interconnection network is always represented by a garph G=(V,E), where the vertices set of G represents processors and the edges set of G represents the links between processors.In the real interconnection network, the number of the processors is huge, so people propose simulating the algorithms of paths and cycles in more complicated interconnection networks.That is the embedding problem. Hypercube and star graph are two popular interconnection networks.The study of embedding paths and cycles in hypercube and star graph has attract many interests.In this paper, we mainly study cycle embedding problems, that is finding all possible lengths of cycles in interconnetion networks.The reliability and fault-tolerance are two important parameters in evaluating the performance of networks.In the real network, there may exist faulty vertices and edges, so it is important to consider faulty networks. That means in the cycle embedding problems, the remaining network can embedding all possible lengths of cycles under the condition that there exists faulty nodes and (or) faulty edges.In this paper, at first, we consider the cycle embedding problem in the conditional faulty edges in star graph, where the conditional faulty means each vertex is incident with at least two fault-free edges. In the second place, we consier the cycle embedding problem in the strongly conditional faulty hypercubes, where the strongly conditional faulty means each vertex in incident with at least three fault-free vertices and at least three fault-free edges. At the same time, because of the hypercube and star garaph are Cayley graphs, we also prove that the Recursive Cube of Rings network RCR(k,r,j)is a class of Cayley graph.The whole paper contains the following parts:In the first chapter, we introduce the background of our works.In the second chapter, we introduce the concepts of graph and network, the definitions of symmetries of graph, the definitions of star graph Sn, hypercube Qn and the Recursive Cube of Rings network RCR(k,r,j), the definition of embedding and the results of star graph and hypercube in embedding problems.In the third chapter, we consider the cycle embedding in star graph Sn (n>4) with conditional faulty edges and get a result. We show that there exists fault-free cycles of all even lengths from6to n! in any n-dimensional star graph Sn (n≥4) with no more than3n-10faulty edges in which each node in incident with at least two fault-free edges.In the fourth chapter, we consider the cycle embedding in hypercube Qn(n≥5) with strongly conditional faulty edges and get a result.We show that every fault-free edge lies on a fault-free cycle of every even length from4to2n-2|Fv|even if the numbers of faulty edges and faulty vertices are no more than2n-5(n≥5)In the fifth chapter, we show that the Recursive Cube of Rings network RCR(k, r, j) is a class of Cayley graph.In the sixth chapter, we get the conclusion of our work and put forward the further considering problems.