Abstract Connectivity is an important parameter to measure fault-tolerance of networks. As a generalization, structure connectivity and substructure connectivity of networks were proposed. For connected graphs $G$ and $H$, the $H$-structure connectivity $\kappa (G; H)$ (resp. $H$-substructure connectivity $\kappa ^{s}(G; H)$) of $G$ is the minimum cardinality of a set of subgraphs $\mathcal{F}$ of $G$ that each is isomorphic to $H$ (resp. a connected subgraph of $H$) such that $G-\mathcal{F}$ is disconnected or the singleton. $n$-dimensional folded cross cube, $FCQ_{n}$, is a network obtained by adding edges to $n$-dimensional cross cubes. In this paper, we study star, path, and cycle structure connectivity and substructure connectivity of $FCQ_{n}$, where $n\geq 8$. For star ($K_{1,m}$) structure, we get that $\kappa (FCQ_{n}; K_{1, m})=\kappa ^{s}(FCQ_{n}; K_{1, m})=\lceil \frac{n + 1}{2} \rceil $ for $2 \leq m \leq \frac{n}{2}$. For path ($P_{k}$) structure, we show that for $3\leq k\leq n+1$, if $k$ is odd, then $\kappa (FCQ_{n}; P_{k})=\kappa ^{s}(FCQ_{n}; P_{k})=\lceil \frac{2(n + 1)}{k+1}\rceil $; if $k$ is even, then $\kappa (FCQ_{n}; P_{k})=\kappa ^{s}(FCQ_{n}; P_{k})=\lceil \frac{2(n + 1)} {k}\rceil $. For cycle ($C_{k}$) structure, we prove that $\kappa ^(FCQ_{n}; C_{k})=\kappa ^{s}(FCQ_{n}; P_{k})$. Further, we calculate $\kappa ^(FCQ_{n}; C_{2k-1})=\lceil \frac{n+1}{k-1} \rceil $ for $4 \leq k \leq n+2$ and $C_{2k}$-structure connectivity of $FCQ_{n}$ is $\lfloor \frac{n+1}{k} \rfloor +1$ for $6 \leq k\leq n + 1$ and even $k$.

Abstract For connected graphs $G$ and $H$, the $H$-structure connectivity $\kappa (G; H)$ (resp. $H$-substructure connectivity $\kappa ^{s}(G; H)$) of $G$ is the minimum cardinality of a set of subgraphs $\mathcal{F}$ of $G$ such that each is isomorphic to $H$ (resp. to a connected subgraph of $H$) so that $G-\mathcal{F}$ is disconnected or singleton. In this paper, we consider $P_t$-structure connectivity and $P_t$-substructure connectivity of augmented $k$-ary $n$-cubes $AQ_{n,k}$ for $n\geq 2$, $k\geq 3$ and $1\leq t\leq 4n-2$. We obtain that $\kappa (AQ_{n,k}; P_t)=\kappa ^s(AQ_{n,k}; P_t)=\frac{4n-2}{t}+1$ for $t\mid 4n-2$, $t\nmid 2n-1$, $t>6$, $n\geq 3$ and $k\geq 4$; $\kappa (AQ_{n,k}; P_t)=\kappa ^s(AQ_{n,k}; P_t)=\lceil \frac{4n-2}{t}\rceil $, in other cases.

Abstract As a generalization of vertex connectivity, for connected graphs $G$ and $T$, the $T$-structure connectivity $\kappa (G; T)$ (resp. $T$-substructure connectivity $\kappa ^{s}(G; T)$) of $G$ is the minimum cardinality of a set of subgraphs $F$ of $G$ that each is isomorphic to $T$ (resp. to a connected subgraph of $T$) so that $G-F$ is disconnected. For $n$-dimensional hypercube $Q_{n}$, Lin et al. showed $\kappa (Q_{n};K_{1,1})=\kappa ^{s}(Q_{n};K_{1,1})=n-1$ and $\kappa (Q_{n};K_{1,r})=\kappa ^{s}(Q_{n};K_{1,r})=\lceil \frac{n}{2}\rceil $ for $2\leq r\leq 3$ and $n\geq 3$ (Lin, C.-K., Zhang, L.-L., Fan, J.-X. and Wang, D.-J. (2016) Structure connectivity and substructure connectivity of hypercubes. Theor. Comput. Sci., 634, 97–107). Sabir et al. obtained that $\kappa (Q_{n};K_{1,4})=\kappa ^{s}(Q_{n};K_{1,4})= \lceil \frac{n}{2}\rceil $ for $n\geq 6$ and for $n$-dimensional folded hypercube $FQ_{n}$, $\kappa (FQ_{n};K_{1,1})=\kappa ^{s}(FQ_{n};K_{1,1})=n$, $\kappa (FQ_{n};K_{1,r})=\kappa ^{s}(FQ_{n};K_{1,r})= \lceil \frac{n+1}{2}\rceil $ with $2\leq r\leq 3$ and $n\geq 7$ (Sabir, E. and Meng, J.(2018) Structure fault tolerance of hypercubes and folded hypercubes. Theor. Comput. Sci., 711, 44–55). They proposed an open problem of determining $K_{1,r}$-structure connectivity of $Q_n$ and $FQ_n$ for general $r$. In this paper, we obtain that for each integer $r\geq 2$, $\kappa (Q_{n};K_{1,r})$ $=\kappa ^{s}(Q_{n};K_{1,r})$ $=\lceil \frac{n}{2}\rceil $ and $\kappa (FQ_{n};K_{1,r})=\kappa ^{s}(FQ_{n};K_{1,r})= \lceil \frac{n+1}{2}\rceil $ for all integers $n$ larger than $r$ in quare scale. For $4\leq r\leq 6$, we separately confirm the above result holds for $Q_n$ in the remaining cases.