The Star-Structure Connectivity and Star-Substructure Connectivity of Hypercubes and Folded Hypercubes. (15th September 2021) - Ba, Lina; Zhang, Heping
Abstract: As a generalization of vertex connectivity, for connected graphs G and T, the T -structure connectivity κ (G; T) (resp. T -substructure connectivity κ ^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 κ (Q_n;K_1, 1)=κ ^s(Q_n;K_1, 1)=n-1 and κ (Q_n;K_1, r)=κ ^s(Q_n;K_1, r)=n2 ceil for 2≤ r≤ 3 and n≥ 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 κ (Q_n;K_1, 4)=κ ^s(Q_n;K_1, 4)= n2 ceil for n≥ 6 and for n -dimensional folded hypercube FQ_n, κ (FQ_n;K_1, 1)=κ ^s(FQ_n;K_1, 1)=n, κ (FQ_n;K_1, r)=κ ^s(FQ_n;K_1, r)= n+12 ceil with 2≤ r≤ 3 and n≥ 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≥ 2, κ (Q_n;K_1, r) =κ ^s(Q_n;K_1, r) =n2 ceil and κ (FQ_n;K_1, r)=κ ^s(FQ_n;K_1, r)= n+12 ceil for all integers n larger than r in quare scale. For 4≤ r≤ 6, we separately confirm the above result holds for Q_n in the remaining cases.