The Star-Structure Connectivity and Star-Substructure Connectivity of Hypercubes and Folded Hypercubes. (15th September 2021)

• Record Type: Journal Article
• Authors: Ba, Lina; Zhang, Heping
• Is Part Of: Computer journal. Volume 65:Number 12(2022)
• Page Start: 3156
• Page End: 3166
• Publication Date: 2021-09-15
• Subjects: structure connectivity -- substructure connectivity -- star graph -- hypercube -- folded hypercube; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab133
• Languages: English
• ISSNs: 0010-4620

Abstract

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.