Structure fault tolerance of hypercubes and folded hypercubes

Let G be a graph and T be a certain connected subgraph of G. The T-structure connectivity κ(G;T) (resp. T-substructure connectivity κs(G;T)) of G is the minimum number of a set of subgraphs F={T1,T2,...,Tm} (resp. F={T1′,T2′,...,Tm′}) such that Ti is isomorphic to T (resp. Ti′ is a connected subgraph of T) for every 1≤i≤m, and F's removal will disconnect G. Let Qn and FQn denote the n-dimensional hypercube and folded hypercube, respectively. In [12], the κ(Qn;T) and κs(Qn;T) were determined for T∈{K1,1,K1,2,K1,3,C4}. In this paper, we generalize the above results by determining κ(Qn;T) and κs(Qn;T) for T∈{Pk,C2k,K1,4} where 3≤k≤n. We also determine κ(FQn;T) and κs(FQn;T) for T∈{Pk,C2k,K1,3} where n≥7 and 2≤k≤n.