Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary n-cube with faulty edges

The k-ary n-cube Q (n) (k) (n a (c) 3/4 2 and k a (c) 3/4 3) is one of the most popular interconnection networks. In this paper, we consider the problem of a faultfree Hamiltonian cycle passing through a prescribed linear forest (i.e., pairwise vertex-disjoint paths) in the 3-ary n-cube Q (n) (3) with faulty edges. The following result is obtained. Let E (0) (not equal a...) be a linear forest and F (not equal= a...) be a set of faulty edges in Q (n) (3) such that E (0) a (c) F = a... and |E (0)| + |F| a (c) 1/2 2n - 2. Then all edges of E (0) lie on a Hamiltonian cycle in Q (n) (3) - F, and the upper bound 2n - 2 is sharp.