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

Thek-aryn-cubeQₙᵏis one of the most attractive interconnection networks for parallel and distributed systems. LetFbe a set of faulty links inQₙᵏand letLbe a linear forest inQₙᵏ-Fsuch that|E(L)|+|F|≤ 2n-3. For any two distinct nodesuandvofQₙᵏwithn≥ 2and oddk≥ 3, we prove thatQₙᵏ-Fadmits a Hamiltonian path betweenuandvpassing throughLif and only if none of the paths inLhasuorvas internal nodes or both of them as end-nodes. The upper bound$2n-3$on$|E(L)|+|F|$is optimal in the worst case. The main results in this paper generalized some known results.