Extraconnectivity of hypercubes

Given a graph G and a non-negative integer g, the g-extraconnectivity of G (written kappa(g)(G)) is the minimum cardinality of a set of vertices of G, if it exists, whose deletion disconnects G, and where every remaining component has more than g vertices. The usual connectivity and superconnectivity of G correspond to kappa(0)(G) and kappa(1)(G), respectively. In this work, we determine kappa(g) (Q(n)) for 0 <= g <= n, n >= 4, where Q(n) denotes the n-dimensional hypercube. (C) 2008 Elsevier Ltd. All rights reserved.