The Graph Embeddings In Faulty K Ary N Cubes

In many parallel computer systems, processors are connected based on an intercon-nection network, popular instances of interconnection networks include Petersen graphs, hypercubes and k ary n cubes. As having many desirable properties, such as ease of im-plementation, low-latency and high-bandwidth interprocessor communication, the k ary n cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. The k ary n cube, denoted by Qnk (k;≥2, n≥1), is a graph consisting of kn vertices. The set of vertices V(Qnk)=｛u0u1…un-1:0≤ui≤k-1,0≤i≤n-1｝. Two vertices u=u0u1…un-1 and v =v0v1…vn-1 are adjacent if and only if there exists an integer j∈｛0,1,…,n-1｝such that uj=vj±1(mod k) and ui=ui for every i∈｛0,1,…,n-l｝\｛j｝.In multiprocessor systems, failures in networks are inevitable. If a network with faulty elements still have some good properties, then the network is faulty-tolerant. Conditional fault-tolerance is to restrict fault distributions in an interconnection network. It means that each vertex in faulty interconnection networks is incident with at least two healthy edges. Graph embedding is a technique that maps a logical graph into a host graph. Many applications, such as architecture simulation, processor allocation, can be modelled as graph embedding. Many graph embeddings take paths and cycles as guest graphs because they are the common structures used to model linear arrays in parallel processing. In this paper,we study the problem of embedding cycles in faulty k ary n cubes. The article is divided into four chapters:In Chapter 1, we introduce some useful basic concepts.In Chapter 2, we consider the longest cycle embedding problem in faulty k ary 2 cubes. Given an even k≥4, let (V1, V2) be the bipartition of the k ary 2 cube and fv1, fv2 be the numbers of faulty vertices in V1 and V2, respectively. We prove that there exists a cycle of length k2 - 2max｛fv1,fv2｝in the k ary 2 cube with at most two faults. This result is optimal with respect to the number of faults tolerated.In Chapter 3, we consider the cycle embedding problem in 3 ary n cubes with condi-tional edge faults. We show that there exists a cycle of any length from 3 to 3n in a 3 ary n cube with at most 2n - 1 edge faults in which each vertex is incident with at least two healthy edges for n≥2 if the subgraph induced by the fault edges is acyclic. This result is optimal with respect to the number of faults tolerated. In Chapter 4, we consider the cycle embedding problem in k ary 2 cubes with condi-tional edge faults and show that there exists a cycle of every even length from 4 toκ2 in a k ary 2 cube with at most 3 edge faults in which each vertex is incident with at least two healthy edges for evenκ≥4. This result is optimal with respect to the number of faults tolerated.