Studies On Problems Of Matchings In Hypercubes Extending To Hamiltonian Cycles

A cycle or path which contains every vertex of a graph is called a Hamiltonian cycle or Hamiltonian path of the graph. A graph is hamiltonian if it contains a Hamiltonian cycle. The problem of determining whether a given graph is a hamilto-nian graph is NP-complete. Embedding hamiltonian cycles or paths into hypercubes and κ-ary n-cubes is a hot topic in the field of graph theory and its applications. It has drawn considerable attention and research, because of a lot of problems in opera-tional research, computer science and coding theory can be converted into Hamilton problem.The n-dimensional hypercube is one of the most popular and efficient intercon-nection networks. There is a large amount of literature on graph-theoretic properties of hypercubes as well as on their applications in parallel computing.In1872. Gros showed for n>2that the n-dimensional hypercube is hamiltonian. Since then, research on hamiltonian cycles in hypercubes satisfying certain additional properties has received considerable attention. Applications in parallel computing inspired the study of hamiltonian cycles in hypercubes with faulty edges.In1993, Ruskey and Savage investigated the hamiltonian cycle embedding prob-lem in Cayley graphs with perfect matchings. They asked the following question: For n≥2, does every matching in n-dimensional hypercube extend to a hamiltonian cycle?Kreweras conjectured for n≥2that every perfect matching of n-dimensional hypercube extends to a hamiltonian cycle. Fink confirmed the conjecture to be true. Also. Fink pointed out that the question of Ruskey and Savage is true for n∈{2.3,4}.Dvorak showed for n≥2that every set of at most2n-3edges of n-dimensional hypercube is contained in a hamiltonian cycle if and only if the edges forming vertex-disjoint paths. This result implies that every matching of at most2n-3edges extends to a hamiltonian cycle in n-dimensional hypercube. In this thesis, we mainly consider the question of Ruskey and Savage. Further-more, since the κ-ary n-cube is a generalization of the n-dimensional hypercube, we investigate the hamiltonian cycle embedding problem in k-ary n-cubes.There are five chapters in this thesis. In Chapter one, we first introduce some basic concepts, terminologies and notations. After that we introduce the background, the question of Ruskey and Savage and the development. At last, we outline the main results obtained in the following chapters.In Chapter two, we firstly investigate the problem of matchings in hypercubes extending to hamiltonian cycles. We show for n≥2that every matching having at most2n-1edges extends to a hamiltonian cycle in n-dimensional hypercube. Furthermore, we generalize the question to faulty hypercubes.After the research of Chapter two, we find that spanning κ-paths play an impor-tant role on the constructions of hamiltonian cycles in hypercubes. In Chapter three, we firstly investigate the structures and properties of the spanning κ-paths in hyper-cubes. Next, we improve the constructions and show for n≥2that every matching having at most3n-10edges extends to a hamiltonian cycle in n-dimensional hyper-cube.Inspired by the idea of Fink, in Chapter four, we firstly investigate the problem that a class of maximal matchings extend to hamiltonian cycles in hypercubes. Next, applying the similar idea, we consider the problem that a class of matchings in at most four dimensions extend to hamiltonian cycles in hypercubes.The κ-ary n-cube is a generalization of the n-dimensional hypercube. It is also one of the most attractive interconnection networks for parallel and distributed systems. In Chapter five, we consider the problem of matchings in κ-ary n-cubes extending to hamiltonian cycles. We show for n≥2and κ≥3that every matching having at most3n-8edges is contained in a hamiltonian cycle in the κ-ary n-cube. Also, we present a perfect matching which is not contained in any hamiltonian cycle in the κ-ary n-cube. This shows that Kreweras’conjecture does not hold for the κ-ary n-cube.