Fault-Free Hamiltonian Cycles Passing through Prescribed Edges in k-Ary n-Cubes with Faulty Edges

The k-ary n-cube Q(n)(k) is one of the most attractive interconnection networks for parallel and distributed systems. In this paper, we consider the problem of a fault-free hamiltonian cycle passing through prescribed edges in a k-ary n-cube Q(n)(k) with some faulty edges. The following result is obtained: For any n >= 2 and k >= 3, let F subset of E(Q(n)(k)), P subset of E(Q(n)(k)) \ F with vertical bar P vertical bar <= 2n - 2, vertical bar F vertical bar <= 2n - (vertical bar P vertical bar + 2). Then there exists a hamiltonian cycle passing through all edges of P in Q(n)(k) - P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths. It improves the result given by Yang and Wang [34].