Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes

Abstract

In this paper, we investigate the fault-tolerant capabilities of the k-ary n-cubes for even integer k with respect to the hamiltonian and hamiltonian-connected properties. The k-ary n-cube is a bipartite graph if and only if k is an even integer. Let F be a faulty set with nodes and/or links, and let k >= 3 be an odd integer. When vertical bar F vertical bar <= 2n - 2, we show that there exists a hamiltonian cycle in a wounded k-ary n-cube. In addition, when vertical bar F vertical bar <= 2n - 3, we prove that, for two arbitrary nodes, there exists a hamiltonian path connecting these two nodes in a wounded k-ary n-cube. Since the k-ary n-cube is regular of degree 2n, the degrees of fault-tolerance 2n - 3 and 2n - 2 respectively, are optimal in the worst case. (c) 2005 Elsevier Inc. All rights reserved.