Fault-Free Hamiltonian Cycles Passing through Prescribed Edges in $k$ -Ary $n$ -Cubes with Faulty Edges
Shurong Zhang, Xianwen Zhang · IEEE Transactions on Parallel and Distributed Systems · 2014
The k-ary n-cube Qnkn 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 Qnkwith some faulty edges. The following result is obtained: For any n ≥ 2 and k ≥ 3, let F ⊂ E(Qnk), P ⊂ E(Qnk) \ F with |P|≤ 2n - 2, |F| ≤ 2n - (|P| + 2). Then there exists a hamiltonian cycle passing through all edges of P in Qnk- F 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].