The star-structure connectivity and star-substructure connectivity of hypercubes and folded hypercubes

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. [6] 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\le r\le 3$ and $n\ge 3$. Sabir et al. [11] obtained that $\kappa (Q_n,K_{1,4})={\kappa }^s(Q_n,K_{1,4})=\lceil \frac{n}{2}\rceil$ for $n\ge 6$, and for $n$-dimensional folded hypercube $F{Q}_n$, $\kappa (F{Q}_n,K_{1,1})={\kappa }^s(F{Q}_n,K_{1,1})=n$, $\kappa (F{Q}_n,K_{1,r})={\kappa }^s(F{Q}_n,K_{1,r})=\lceil \frac{n+1}{2}\rceil$ with $2\le r\le 3$ and $n\ge 7$. They proposed an open problem of determining $K_{1,r}$-structure connectivity of $Q_n$ and $F{Q}_n$ for general $r$. In this paper, we obtain that for each integer $r\ge 2$, $\kappa (Q_n;K_{1,r})={\kappa }^s(Q_n;K_{1,r})=\lceil \frac{n}{2}\rceil$ and $\kappa (F{Q}_n;K_{1,r})={\kappa }^s(F{Q}_n;K_{1,r})=\lceil \frac{n+1}{2}\rceil$ for all integers $n$ larger than $r$ in quare scale. For $4\le r\le 6$, we separately confirm the above result holds for $Q_n$ in the remaining cases.

Cited by in corpus (1)

• Star Structure Connectivity of Folded hypercubes and Augmented cubes