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

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 |F|⩽2n-2, we show that there exists a hamiltonian cycle in a wounded k-ary n-cube. In addition, when |F|⩽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.