Super Connectivity of Component-Composition Networks

The reliability of an interconnection network is an important issue for multiprocessor systems. The super connectivity is a novel measure for the reliability of an interconnection network. Given a graph G, the super connectivity of G is the minimum cardinality of vertices whose removal results in a disconnected graph that contains no isolated vertex. This paper studies the super connectivity of component-composition networks, which includes burnt pancake graphs, star graphs, bubble-sort graphs, pancake graphs, hypercube-like graphs, and so on. We also apply the obtained result for the component composition networks to determine the super connectivity of various known networks. For instance, we determine that the super connectivity of the n-dimensional burnt pancake graph BPn is 2n-2 for n ≥2.