On g -extra connectivity of hypercube-like networks

Citation data:

Journal of Computer and System Sciences, ISSN: 0022-0000, Vol: 88, Page: 208-219

Publication Year:
Usage 1
Abstract Views 1
Captures 3
Readers 3
Social Media 1
Shares, Likes & Comments 1
Jin-Xin Zhou
Elsevier BV
Mathematics; Computer Science
article description
Given a connected graph G and a non-negative integer g, the g-extra connectivity κ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 κg(Xn)=fn(g) holds, where Xn is an n -dimensional HL-network, fn(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 κg(Xn)≥fn(g) holds for n≥5 and 0≤g≤n−3. This enables us to give a sufficient condition for the equality κg(Xn)=fn(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.