Structure connectivity of hypercubes

Abstract

The connectivity of a graph is an important measurement for the fault-tolerance of the network. To provide more accurate measures for the fault-tolerance of networks than the connectivity, some generalizations of connectivity have been introduced. Let H be a connected subgraph of a graph G . A set F of a connected subgraphs of G is called a subgraph cut of G if G − F is either disconnected or trivial. If further, each member of F is isomorphic to H , then F is called an H -structure cut of G. The H -structure connectivity κ ( G ; H ) of G is the minimum cardinality of an H -structure cut of G . In this paper we determine κ ( Q n ; H ) or its upper bound where Q n is the n -dimensional hypercube with n ≥ 4 and H is either Q m with m ≤ n − 2 or even cycle C l with l ≤ 2 n . Keywords: Structure connectivity, Cycle, Hypercube