Paths And Cycles In The K-Ary N-Cube

Advances in technology, especially the advent of VLSI circuit technology, have made it possible to build a large parallel and distributed system involving thousands or even tens of thousands of processors. One crucial step on designing a large-scale parallel and distributed system is to determine the topology of the interconnection network (network for short). The network topology not only affects the hardware architecture but also the nature of the system software that can be used in a parallel and distributed system. Theκ-ary n-cube network is a kind of most important networks. Many interconnection networks can be viewed as the subclasses of Qnk include the cycle, the torus and the hypercube. On the other hand, some of massively parallel systems have been built with aκ-ary n-cube forming the underlying topology, such as the Cray T3D [1], J-machine [2] and the iWarp [3].For interconnection networks, the problem of simulating one network by another is modelled as a network embedding problem. Linear arrays and rings, which are two of the most fundamental interconnection networks for parallel and distributed computation, are suitable to develop simple and efficient algorithms with low communication costs. The wide applications of linear arrays and rings motivate us to investigate path and cycle embedding in networks. In this paper, we consider the problem of embedding paths and cycles in theκ-ary n-cube network.This thesis consists of five chapters. In Chapter 1, after a short introduction to the used basic notation and terminology on graphs, a survey on the application background and the research advance of the problem of embedding paths and cycles in theκ-ary n-cube network are given. Finally, the main results acquired in this thesis are listed.In path embedding problems, finding parallel paths among nodes in interconnection networks is one of most central issues concerned with efficient data transmission. Chapter 2 focuses on many-to-many (un)paired disjoint path covers of hypercubes. Let G be a graph. For a set S={s1,s2,…,sκ} ofκsources and a set T={t1,t2,…,tκ} ofκsinks in V{G), the many-to-manyκ-disjoint path problem is to determine whether there existκdisjoint (S, T)-paths each joining a source si and a sink tψ(i), whereψis some permutation on the set {1,2,…,κ}. A disjoint path cover of a graph G is a set of disjoint paths containing all the vertices of G. In Chapter 2, we discuss the structure properties of hypercubes, generalize a result given by Xiebin Chen et al. [4] and show that for any two sets S and T of n vertices in different parts, the hypercube Qn has many-to-many unpaired n-disjoint (S, T)-path covers except the case when there exists a vertex v such that NQn (v)= S and v (?) T or NQn (v)= T and v (?) S.Since node faults and/or link faults may occur to networks, it is significant to consider faulty networks. Fault tolerance ability is an important consideration for interconnection network topology. That is, the network is still functional when some node faults and/or link faults occur. Among them, two fault models were adopted; 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, whereas the conditional fault model assumed that the distribution of faults must satisfy some properties. It is more difficult to solve problems under the conditional fault model than the random fault model.We denote the node set and the edge set of G as V(G) and E(G), respectively. The graph G is said to be pancyclic if it contains a cycle of every length from the girth g(G) to |V(G)| in G, and bipancyclic if it contains a cycle of every even length from 4 to |V(G)|. Furthermore, a bipancyclic graph G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. The pancyclicity and bipancyclicity are important measurements to determine if a network topology is suitable for an application where mapping cycles of any length into the network topology is required. Chapters 3 and 4 are devoted to study the edge-bipancyclity ofκ-ary n-cube networks under the random fault model and the pancyclity under the conditional fault model, respectivley. In Chapter 3, we prove that theκ-ary n-cube is edge-bipancyclic for oddκ≥3 and nearly edge-bipancyclic for evenκ> 4. The result answers the question proposed by Iain A. Stewart et al. in [5]. In Chapter 4, we show that the 3-ary n-cube is conditional (4n-5)-fault pancyclic for n≥3. In the last part of Chapter 3 and Chaper 4, we respectively show that our result can not be improved in some sense.In 2006, Caha and Koubek investigated the existence of a Hamiltonian cycle of an n-dimensional hypercube passing through a set of prescribed edges, which is in a sense complementary to the last problem mentioned above. Since then, research on Hamiltonian paths and cycles in hypercubes with prescribed edges has received considerable attention. In Charper 5, we consider the prescribed hamiltonian-connectivity of the 3-ary n-cube. Given a set P of at most 2n-2 prescribed edges of a 3-ary n-cube, n>2, satisfying the condition that the subgraph induced by P consists of pairwise vertex-disjoint paths, and given two vertices u and v such that none of the paths of the subgraph induced by P have u or v as internal vertices or both of them as end-vertices, we describe a construction of a hamiltonian path from u to v passing through every edge of this set. Thus Qn3 has a hamiltonian cycle passing through an edge set P if and only if P is a linear set and |P|≤2n-1.