Star-structure connectivity of folded hypercubes and augmented cubes

The connectivity is an important parameter to evaluate the fault-tolerance 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. a connected subgraph of H) so that G - F is disconnected or the singleton. In this paper, we compute the star (K-1,K-m)-structure connectivity of n-dimensional folded hypercubes FQ(n) and augmented cubes AQ(n), which are popular variants of n-dimensional hypercubes Q(n) as attractive interconnection network prototypes for multiple processor systems. By a large component approach, we obtain that kappa(FQ(n); K-1,K-m) = kappa(s)(FQ(n); K-1,K-m) = inverted right perpendicular n+1/2 inverted left perpendicular for 2 <= m <= n - 1, n >= 7 and kappa(AQ(n); K-1,K-m) = kappa(s)(AQ(n); K-1,K-m) = inverted right perpendicular n-1/2 inverted left perpendicular for 4 <= m <= 3n-15/4 which much improve some known results with very restricted m.