Hamiltonian Paths of k-ary n-cubes Avoiding Faulty Links and Passing Through Prescribed Linear Forests

The k-ary n-cube Q(n)(k) is one of the most attractive interconnection networks for parallel and distributed systems. Let F be a set of faulty links in Q(n)(k) and let L be a linear forest in Q(n)(k) - F such that vertical bar E(L)vertical bar + vertical bar F vertical bar <= 2n - 3. For any two distinct nodes u and v of Q(n)(k) with n >= 2 and odd k >= 3, we prove that Q(n)(k) - F admits a Hamiltonian path between u and v passing through L if and only if none of the paths in L has u or v as internal nodes or both of them as end-nodes. The upper bound 2n - 3 on E(L)vertical bar + vertical bar F vertical bar is optimal in the worst case. The main results in this paper generalized some known results.