Let H be a connected subgraph of a graph G. The H-structure connectivity $\kappa (G;H)$ of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to H. Similarly, the H-substructure connectivity ${\kappa }^s(G;H)$ of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of H. Structure connectivity and substructure connectivity generalise the classic connectivity. Let $P_n$ and $B{P}_n$ be the n-dimensional pancake graph and n-dimensional burnt pancake graph, respectively. In this paper we show $\kappa (P_n;K_{1,t_1})={\kappa }^s(P_n;K_{1,t_1})=n-1(1\le t_1\le n-2)$, and $\kappa (B{P}_n;K_{1,t_2})={\kappa }^s(B{P}_n;K_{1,t_2})=n(1\le t_2\le n-1)$.

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.