Star Structure Connectivity of Folded hypercubes and Augmented cubes

Abstract

The connectivity is an important parameter to evaluate the robustness of a network. As a generalization, structure connectivity and substructure connectivity of graphs 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 $F$ of $G$ that each is isomorphic to $H$ (resp. to a connected subgraph of $H$) so that $G-F$ is disconnected or the singleton. As popular variants of hypercubes, the $n$-dimensional folded hypercubes $F{Q}_n$ and augmented cubes $A{Q}_n$ are attractive interconnected network prototypes for multiple processor systems. In this paper, we obtain that $\kappa (F{Q}_n;K_{1,m})={\kappa }^s(F{Q}_n;K_{1,m})=\lceil \frac{n+1}{2}\rceil$ for $2⩽m⩽n-1$, $n⩾7$, and $\kappa (A{Q}_n;K_{1,m})={\kappa }^s(A{Q}_n;K_{1,m})=\lceil \frac{n-1}{2}\rceil$ for $4⩽m⩽\frac{3n-15}{4}$.

References in corpus (2)

• The star-structure connectivity and star-substructure connectivity of hypercubes and folded hypercubes
• Fault-tolerant analysis of augmented cubes