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

摘要

The k-aiy n-cube Q_n~k (n ≥ 2 and k ≥ 3) is one of the most popular interconnection networks. In this paper, we consider the problem of a fault-free 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 (≠ 0) be a linear forest and F (≠ 0) be a set of faulty edges in Q_n~3 such that E_0 ∩ F = 0 and ∣E_0∣ + |F| ≤ 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.