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 be a connected subgraph of a graph . A set of a connected subgraphs of is called a subgraph cut of if is either disconnected or trivial. If further, each member of is isomorphic to , then is called an -structure cut of G. The -structure connectivity of is the minimum cardinality of an -structure cut of . In this paper we determine or its upper bound where is the -dimensional hypercube with and is either with or even cycle with .

Keywords

• structure connectivity
• cycle
• hypercube