Path-embeddability And Fault-tolerance Of The K-Ary N-Cube

With the development of the computer applications, there is an urgent need to improve the computing power and performance of computer systems. This reason has motivated the research on the parallel and distributed systems. The mode of connection between system components is called a interconnection network of the system, or network for short. Obviously, the functions of parallel and distributed systems are heavily dependent upon the interconnection networks of the systems. The k-ary n-cube as one of the most attractive interconnection networks, has drawn considerable research attention for its desirable properties, such as ease of imple-mentation, low-latency and high-bandwidth inter-processor communication. Sev-eral parallel and distributed systems, such as iWarp,Cray T3D and the Blue Gene/L torus, have been built based on the k-ary n-cube.An interconnection network may be modeled by a simple graph whose vertices represent components of the network and whose edges represent physical communi-cation links. Such a graph is called the topological structure of the interconnection network, or network topology for short. The path is one of the most fundamental and the most important network topologies because of its simple structure. Then, path embeddings is an important problem that must be considered in network de-sign. Therefore, the problem of embedding paths into interconnection networks has drawn much attention. With the increasing number of components in the network, especially the very large scale computer network, failures (faulty components or communication channels) are inevitable. The fault tolerance ability is that the net-work is still functional when some faults occur. In many cases, people hope that the damaged network has as many good properties as possible. Thus, fault tolerance of interconnection networks has become an important issue. In this paper, we consider the path-embeddability and fault tolerance of the k-ary n-cube networks.The thesis consists of five chapters. In Chapter1, after a brief introduction to the background and significance of this work, some basic concepts and terminology on graphs and the research advance of the related works are given. Finally, the main results acquired in this thesis are listed.In path embedding problems, finding disjoint paths has received much attention because of its numerous applications in high performance interconnection networks. In disjoint path problems, the many-to-many disjoint path problem is the most important one. Chapter2focuses on many-to-many unpaired disjoint path covers of k-ary n-cubes, where even k≥4. The k-ary n-cube is bipartite if and only if k is even. Let (X, Y) be a bipartition of the k-ary n-cube. For two sets S(?)X and T(?)Y such that|S|=|T|=m, where1≤m<2n-1, we prove that there exist m disjoint (S, T)-paths each joining a vertex in S and a vertex in T and these m disjoint paths contain all vertices of the k-ary n-cube. This generalizes some of the results in [4].There are two fault models; one is the random fault model, and the other is the conditional fault model. The random fault model assumed that the faults might occur everywhere without any restriction, and the conditional fault model assumed that the distribution of faults must satisfy some properties. In Chapters3,4and5, we investigate the fault tolerance of the k-ary n-cube with faults or conditional faults.Let G be a bipartite graph with bipartition (V0,V1). G is said to be hamil-tonian laceable if there is a hamiltonian path between every pair of vertices which are in different parts. Lewinter and Widulski introduced the concept of hyper hamiltonian laceability. G is hyper hamiltonian laceable if it is hamiltonian laceable and, for any three vertices v∈Vi and s,t∈V1-i, there is a hamiltonian st-path in G-v, where i∈{0,1}. Since a bipartite graph is not hamiltonian connected, it is important to investigate the hamiltonian laceability and hyper hamiltonian laceabil-ity of bipartite graphs. Let k≥4be an even integer. In Chapter3, we prove that the k-ary n-cube with at most2n-3faulty edges is hyper hamiltonian laceable. In Chapter4, we prove that the conditional faulty k-ary n-cube with at most4n-5faulty edges is hamiltonian laceable. In the last part of Chapter3and Chapter4, we respectively give some examples which show that our results can not be improved in some sense.Pancyclicity is an important measurement for determining if a network topol- ogy can handle applications in which it is necessary to map rings of any length into the topology. We denote the node set of G by V(G). The graph G is said to be bipancyclic if G contains a cycle of every even length from4to|V(G)|. Further-more, edge-bipancyclicity is an more refined measure to evaluate an interconnection networks. A bipancyclic graph G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length from4to|V(G)|. The edge-bipancyclicity of a graph is one of the most important cycle embedding problems. In Chapter5, we prove that in the conditional faulty k-ary n-cube Qnk (even k≥4), every healthy edge is contained in fault-free cycles of even lengths from6to|V(Qnk)|, even if the Qnk has up to4n-5edge faults.