2020/02/24 by Chen, Yihan, Zhang, Bicheng
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2002.10134
Hypercube is one of the most important networks to interconnect processors in multiprocessor computer systems. Different kinds of connectivities are important parameters to measure the fault tolerability of networks. Lin et al.\citeLinStructure introduced the concept of H-structure connectivity κ(Qn;H) (resp. H-substructure connectivity κs(Qn;H)) as the minimum cardinality of F=\H1,…,Hm\ such that Hi (i=1,…,m) is isomorphic to H (resp. F=\H'1,…,H'm\ such that H'i (i=1,…,m) is isomorphic to connected subgraphs of H) such that Qn-V(F) is disconnected or trivial. In this paper, we discuss κ(Qn;H) and κs(Qn;H) for hypercubes Qn with n≥ 3 and H∈ \Pk,Ck|3≤ k≤ 2n-1\. As a by-product, we solve the problem mentioned in \citeManeStructure.