| The interconnection network provides an effective mechanism for exchanging data between processors in a parallel computing system. An interconnection network is usu-ally represented as a graph, where nodes and edges correspond processors and commu-nication links between processors, respectively. As the size of a parallel computing system increases, it becomes much likely that there exist faulty processors and faulty communication links in such a system. Consequently, the graph-embedding ability of an interconnection network should be studied in the situation where faulty elements arise.With the continuous development of the Internet, there have been many new net-work including the k-ary n-cube network. In this paper, we investigate the fault-tolerant capabilities and the conditional fault-tolerant capabilities of Qkn for odd integer k with respect to the pancyclicity. This text consists of four chapters, The second chapter and the third chapter of which are the main parts of this article.The first chapter is the introduction, which introduces the concepts of graph theory and the network, describes the present research situation at home and abroad, explains the basis and significance of this article topics. It also presents the definition of the Qkn and its related properties. What’s more, some of the conclusions about the fault-tolerant pancyclic of Qkn are included.In the second chapter, we investigate the fault-tolerant capabilities of the k-ary n-cubes for odd integer k>3with respect to the pancyclicity. Let F be the set of faulty set with nodes and/or links, Fu be the set of all faulty vertices, and odd k>3,|F|<2n-2. At first, we show that, Qk2-F contains a cycle of lengthl, k<l <|V(Qk2)-Fv|when n=2,|F|<2. Then, by the induction on n, we prove that there exists a cycle of every length l, k<l<kn-|FV|in Qkn-F.In the third chapter, we investigate the pancyclicity of the k-ary n-cubes with conditional faulty edges. Since Qkn can be divided into k Qkn-1-subgraphs, without loss of generality, let one of them be Q[O], we show the conclusion in three subcase. If there is no ambiguities, let F be a set of faulty edges such that|F|<4n-5and each vertex of V(Qkn-F) is incident with at least two fault-free edges. We show that Qkn-F has a cycle of length from k to|V(Qkn)|. Furthermore, our result is optimal.In the fourth chapter, we give a conclusion and show the problems that can be studied in the future. |
