Hamiltonian Paths of -cubes Avoiding Faulty Links and Passing Through Prescribed Linear Forests
Yuxing Yang, Lingling Zhang
Abstract
The <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -ary <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> -cube <inline-formula><tex-math notation="LaTeX">$Q_n^k$</tex-math></inline-formula> is one of the most attractive interconnection networks for parallel and distributed systems. Let <inline-formula><tex-math notation="LaTeX">$F$</tex-math></inline-formula> be a set of faulty links in <inline-formula><tex-math notation="LaTeX">$Q_n^k$</tex-math></inline-formula> and let <inline-formula><tex-math notation="LaTeX">$L$</tex-math></inline-formula> be a linear forest in <inline-formula><tex-math notation="LaTeX">$Q_n^k-F$</tex-math></inline-formula> such that <inline-formula><tex-math notation="LaTeX">$|E(L)|+|F|\leq 2n-3$</tex-math></inline-formula> . For any two distinct nodes <inline-formula><tex-math notation="LaTeX">$u$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$v$</tex-math></inline-formula> of <inline-formula><tex-math notation="LaTeX">$Q_n^k$</tex-math></inline-formula> with <inline-formula><tex-math notation="LaTeX">$n\geq 2$</tex-math></inline-formula> and odd <inline-formula><tex-math notation="LaTeX">$k\geq 3$</tex-math></inline-formula> , we prove that <inline-formula><tex-math notation="LaTeX">$Q_n^k-F$</tex-math></inline-formula> admits a Hamiltonian path between <inline-formula><tex-math notation="LaTeX">$u$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$v$</tex-math></inline-formula> passing through <inline-formula><tex-math notation="LaTeX">$L$</tex-math></inline-formula> if and only if none of the paths in <inline-formula><tex-math notation="LaTeX">$L$</tex-math></inline-formula> has <inline-formula><tex-math notation="LaTeX">$u$</tex-math></inline-formula> or <inline-formula><tex-math notation="LaTeX">$v$</tex-math></inline-formula> as internal nodes or both of them as end-nodes. The upper bound <inline-formula><tex-math notation="LaTeX">$2n-3$</tex-math></inline-formula> on <inline-formula><tex-math notation="LaTeX">$|E(L)|+|F|$</tex-math></inline-formula> is optimal in the worst case. The main results in this paper generalized some known results.