Structure connectivity and substructure connectivity of twisted hypercubes

Abstract

Let $G$ be a graph and $T$ a certain connected subgraph of $G$. The $T$-structure connectivity $\kappa (G;T)$ (or resp., $T$-substructure connectivity ${\kappa }^s(G;T)$) of $G$ is the minimum number of a set of subgraphs $\mathcal{F}=\{T_1,T_2,\dots ,T_m\}$ (or resp., $\mathcal{F}=\{T_1^{{}^{\prime }},T_2^{{}^{\prime }},\dots ,T_m^{{}^{\prime }}\}$) such that $T_i$ is isomorphic to $T$ (or resp., $T_i^{{}^{\prime }}$ is a connected subgraph of $T$) for every $1\le i\le m$, and $\mathcal{F}$'s removal will disconnect $G$. The twisted hypercube $H_n$ is a new variant of hypercubes with asymptotically optimal diameter introduced by X.D. Zhu. In this paper, we will determine both $\kappa (H_n;T)$ and ${\kappa }^s(H_n;T)$ for $T\in \{K_{1,r},P_k\}$, respectively, where $3\le r\le 4$ and $1\le k\le n$.

19 pages, 2 figures