On g-extra connectivity of hypercube-like networks

Given a connected graph G and a non-negative integer g, the g-extra connectivity kappa(g)(G) of G is the minimum cardinality of a set of vertices in G, if it exists, whose deletion disconnects G and leaves each remaining component with more than g vertices. This paper focuses on the g-extra connectivity of hypercube-like networks (HL-networks for short). All the known results suggest the equality kappa(g)(X-n) = f(n)(g) holds, where X-n is an n-dimensional HL-network, f(n)(g) = n(g + 1) - g(g+3)/2, n >= 5 and 0 <= g <= n - 3. However, in this paper, we show that this equality does not hold in general. We also prove that kappa(g)(X-n) >= f(n)(g) holds for n >= 5 and 0 <= g <= n - 3. This enables us to give a sufficient condition for the equality kappa(g)(X-n) = f(n)(g), which is then used to determine the g-extra connectivity of HL-networks for some small g or the g-extra connectivity of some particular subfamily of HL-networks. (C) 2017 Elsevier Inc. All rights reserved.