Structure Fault-Tolerant Hamiltonian Cycle and Path Embeddings in Bipartite $k$-Ary $n$-Cube Networks
Eminjan Sabir, Jianxi Fan, Jixiang Meng, Baolei Cheng · IEEE Transactions on Reliability · 2023
One of the important issues in evaluating an interconnection network is to study the fault-tolerant Hamiltonian cycle and Hamiltonian path embedding problems. The$k$-ary$n$-cube (denoted by$Q^{k}_{n}$) networks are used as interconnection networks for many parallel and distributed computing systems. In this article, we investigate the Hamiltonian cycle and path embeddings in the bipartite$k$-ary$n$-cube$Q^{k}_{n}$based on$K_{1,1}$-structure faults. We show that there exists a Hamiltonian cycle in$Q^{k}_{n}-\mathcal {F}$if$|\mathcal {F}|\leq 2n-2$and there exists a Hamiltonian path between any two vertices from different partite sets in$Q^{k}_{n}-\mathcal {F}$if$|\mathcal {F}|\leq 2n-3$for$n\geq 2$and even$k\geq 4$, where$\mathcal {F}$is a set of vertex-disjoint subgraphs isomorphic to$K_{1,1}$in$Q_{n}^{k}$. In some sense, the results mean that when a subset$S$of at most$4n-4$(resp.$4n-6$) processors is deleted from a bipartite$Q^{k}_{n}$, there exists a Hamiltonian cycle (resp. a Hamiltonian path between any two healthy processors from different partite sets) in the remaining network. Our results, in some sense, compensate the results in Lv et al. [J. Parallel Distrib. Comput., 120, 148–158, 2018] and [Comput. J., 60, 159–179, 2017], where authors studied the$K_{1,3}$-substructure fault-tolerant Hamiltonian cycle and path embedding problems in nonbipartite$k$-ary$n$-cubes. In comparison, the bipartite$k$-ary$n$-cube$Q^{k}_{n}$can keep the same$K_{1,1}$-structure fault-tolerant Hamiltonian capabilities as the nonbipartite one.