Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951161 | Journal of Computer and System Sciences | 2017 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jin-Xin Zhou,