Component connectivity of the hypercubes

Abstract

The r-component connectivity kappa(r)(G) of the non- complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. So, kappa(2) is the usual connectivity. In this paper, we determine the r-component connectivity of the hypercube Q(n) for r = 2, 3, ..., n + 1, and we classify all the corresponding optimal solutions.