Structure and substructure connectivity of folded divide-and-swap cube

Abstract

Let $H$ be a connected subgraph of a graph $G$. The structure connectivity of $G$, denoted by $\kappa (G;H)$, is the minimum number of a set of connected subgraphs in $G$, whose removal disconnects $G$ and each element in the set is isomorphic to $H$. The substructure connectivity of $G$, denoted by ${\kappa }^s(G;H)$, is the minimum number of a set of connected subgraphs in $G$, whose removal disconnects $G$ and each element in the set is isomorphic to a connected subgraph of $H$. In this paper, we determine $H$-structure connectivity and $H$-substructure connectivity of folded divide-and-swap cube $FDS{C}_n$ for $H\in \{K_1,K_{1,1},K_{1,m}(2\le m\le d+1)\}$ where $n=2^d$. We show that $\kappa (FDS{C}_n;K_1)={\kappa }^s(FDS{C}_n;K_1)=d+2$, $\kappa (FDS{C}_n;K_{1,1})={\kappa }^s(FDS{C}_n;K_{1,1})=d+1$ for $d\ge 1$ and $\kappa (FDS{C}_n;K_{1,m})={\kappa }^s(FDS{C}_n;K_{1,m})=\lfloor \frac{d}{2}\rfloor +1$ for $d\ge 1$ and $2\le m\le d+1$.