Hamiltonian Paths of -cubes Avoiding Faulty Links and Passing Through Prescribed Linear Forests
Yuxing Yang, Lingling Zhang · IEEE Transactions on Parallel and Distributed Systems · 2021
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$|E(L)|+|F|\leq 2n-3$. For any two distinct nodes$u$and$v$of$Q_n^k$with$n\geq 2$and odd$k\geq 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)|+|F|$is optimal in the worst case. The main results in this paper generalized some known results.