Cycle Embedding And Path Embedding In Several Interconnection Networks

Interconnection network is usually represented by a simple graph, where vertices represent processors and edges represent communication links between processors. On the contrary, graph is also regarded as the topological structure of some interconnection network. Graph and interconnection network are the same in the sense of topological structure. In this thesis, we do not distinguish "graph" and "interconnection network". When evaluate an interconnection network, one major concern is its graph embedding ability. The graph embedding is a technique that find another graph (named guest graph) in a graph (named host graph) as its subgraph. In this thesis, the "embedding" means finding a subgraph in a given interconnection network. Path and cycle are two of the most fundamental structures for parallel and distributed computation. The cycle (re-spectively, path) embedding problem deals with finding given lengths of cycles (respec-tively, paths) in a given graph. As the size of an interconnection network increases, it becomes more likely that processors and communication links are disabled. Hence, it is important to consider interconnection networks with faulty elements. Embedding path and cycle into a faulty interconnection network is an important issue in parallel pro-cessing. Fault-tolerant cycle embedding (or path embedding) is finding given lengths of fault-free cycles (or paths) in interconnection networks with faulty elements.This thesis is organized as follows.In Chapter1, we gave a brief introduction on the background of cycle embedding and path embedding in interconnection networks.In Chapter2, we introduce some concepts of several interconnection networks related to this thesis.In Chapter3, we study fault-tolerant cycle embedding in hypercubes with faulty edges. We consider the n-dimensional hypercube Qn with at most3n-8faulty edges and n≥5under the following two conditions:(1) each vertex is incident to at least two fault-free edges, and (2) every4-cycle does not have any pair of non-adjacent vertices whose degrees are both two after removing the faulty edges, and prove that there exists a fault-free cycle of every even length from4to2" in Qn. This result improves Liu and Wang’s result, who proved that under the same number of faulty edges and conditions (1) and (2), there is a fault-free Hamiltonian cycle in Qn。In Chapter4, we study cycles embedding on folded hypercubes. Firstly, we study the vertex fault-tolerant cycle embedding in folded hypercubes. Let FFv be the set of faulty vertices in an n-dimensional folded hypercube FQn. We consider FQn with|FFv|≤n-2and prove that if n≥3, then every fault-free edge of FQn lies on a fault-free cycle of every even length from4to2"-2|FFv|, and if n≥2and n is even, then every fault-free edge of FQn lies on a fault-free cycle of every odd length from n+1to2n-2|FFv|-1. This result improves Hsieh et al’s result in the sense of the number of fault-tolerant vertices and the property of cycle embedding. They considered the FQn with|FFV|=1faulty vertices and proved that (1):if n≥3, then there is a fault-free cycle of every even length from4to2"-2in FQn-FFv; and (2) if n≥2and n is even, then there is fault-free cycle of every odd length from n+1to2n-1in FQn.Secondly, we study odd cycle embedding in folded hypercubes with conditional faults. Let FQn be an n-dimensional folded hypercube with|FFe|≤2n-5faulty edges such that each vertex is incident to at least two fault-free edges, where n≥4and n is even. We prove that every edge of FQn-FFe lies on a fault-free cycle of every odd length from n+1to2n-1.Thirdly, we study edge fault-tolerant even cycle embedding on folded hypercubes with conditional faults. Let FQn be an n-dimensional folded hypercube with|FFe|≤2n-4faulty edges such that each vertex is incident to at least two fault-free edges, where n≥5. We prove that every edge of FQn-FFe lies on a fault-free cycle of every even length from6to2-.The above two results improves Xu et al’s result in the sense of the number of fault-tolerant edges. They considered FQn with｜FFe｜≤n-1faulty edges and proved that every edge of FQn-FFe lies on a fault-free cycle of every even length from4to2n; and when n is even, every edge of FQn-FFe lies on a fault-free cycle of every odd length from n+1to2n-1。In Chapter5, we study conditional edge-fault pancyclicity of augmented cubes. We consider the n-dimensional augmented cube AQn (n≥3) with at most4n-12faulty edges such that each vertex is incident to at least two fault-free edges. We prove that the AQn contains fault-free cycles of lengths from3to2n. This result improves Ma et al’s result in the sense of the number of fault-tolerant edges. They considered the AQn (n≥2) with no more than2n-3faulty edges and proved that AQn contains every fault-free cycle of every length from3to2n.In Chapter6, we study the path embedding and cycle embedding properties in balanced hypercubes.Firstly, we consider the two vertex disjoint paths in balanced hypercubes. Let X and Y be the bipartite vertex sets of an n-dimensional balanced hypercube BHn, where n≥1. Let u and x be two different vertices of X and v and y be two different vertices of Y. We prove that there exist two vertex disjoint paths P[x, y] and R[u, v] in BHn such that V(P[x, y]) U V(R[u, v])=V(BHn). From this result, we can get a corollary that BHn (n≥1) is Hamiltonian laceable, which was proved by Xu et al.Secondly, we study vertex fault-tolerant cycles embedding in balanced hypercubes. Let Fv be the set of an n-dimensional balanced hypercubes BHn with|FV|≤n-1faulty vertices, where n≥1. We prove that every fault-free edge of BHn lies on a fault-free cycle of every even length from4to22n-2|Fv|.Thirdly, we study edge fault-tolerant cycle embedding in balanced hypercube. We consider the n-dimensional balanced hypercube with｜Fe｜≤2n-3faulty edges, where n>2. We prove that every fault-free edge lies on a fault-free cycle of every even length from6to22n.The above two results improves Xu et al’s result in the sense of the number of fault-tolerant vertices and fault-tolerant edges. They proved that under fault-free condition, every edge of BHn (n≥1) lies on a cycle of every even length from4to22n.In Chapter7, we propose some problems to be solved.