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}|\le 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}|\le 2n-3$ for $n\ge 2$ and even $k\ge 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.

One of the important issues in evaluating an interconnection network is to study the hamiltonian cycle embedding problems. A graph G is spanning k-edge-cyclable if for any k independent edges $e_1,e_2,\dots ,e_k$ of G, there exist k vertex-disjoint cycles $C_1,C_2,\dots ,C_k$ in G such that $V\left(C_1\right)\cup V\left(C_2\right)\cup \cdots \cup V\left(C_k\right)=V\left(G\right)$ and $e_i\in E\left(C_i\right)$ for all $1\le i\le k$. According to the definition, the problem of finding hamiltonian cycle focuses on $k=1$. The notion of spanning edge-cyclability can be applied to the problem of identifying faulty links and other related issues in interconnection networks. In this paper, we prove that the n-dimensional hypercube $Q_n$ is spanning k-edge-cyclable for $1\le k\le n-1$ and $n\ge 2$. This is the best possible result, in the sense that the n-dimensional hypercube $Q_n$ is not spanning n-edge-cyclable.