Search

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.