Characterizations of Minimum Structure- and Substructure-Cuts of Hypercubes. (3rd November 2018) - Yang, Yuxing
Abstract: For a graph G and a connected subgraph H of G, denote by ℋ ( G ; H ) the set of subgraphs of G which are isomorphic to H and denote by ℋ S ( G ; H ) the union of sets of subgraphs of T, where T ranges over all the elements in ℋ ( G ; H ) . An H -structure-cut (respectively, H -substructure-cut) of G is a subset of ℋ ( G ; H ) (respectively, ℋ S ( G ; H ) ), if any, whose removal disconnects G . The H -structure connectivity (respectively, H -substructure connectivity) is the cardinality of a minimum H -structure-cut (respectively, H -substructure-cut) of G . The hypercube is one of the most attractive interconnection networks for large-scale multiprocessor computer systems. In this paper, we will characterize the minimum H -structure-cuts and the minimum H -substructure-cuts of hypercubes for H ∈ { K 1, 1, K 1, 2, K 1, 3, C 4 } .