h-extra r-component connectivity of interconnection networks with application to hypercubes

The connectivity and its generalizations have been well studied due to their impact on the fault tolerance and diagnosability of the interconnection networks. In this paper, we introduce a novel generalized connectivity, which combines the h-extra connectivity and r-component connectivity. Given a connected graph G = (V, E), for any h >= 0 and r >= 2, an h-extra r-component cut of G is a subset S subset of V such that there are at least r components in G \ S and each component has at least h +1 vertices; h-extra r-component connectivity of G, denoted as C kappa(h)(r)(G), is the minimum size of any h-extra r-component cut of G. We determine the h-extra r-component connectivity of n-dimensional hypercube Q(n), C kappa(1)(r) (Q(n)) = 2(r - 1)(n - r +1) for r is an element of {2,3, 4}. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

The paper introduces a novel generalized connectivity that combines h-extra connectivity and r-component connectivity. The h-extra r-component connectivity of n-dimensional hypercube Q(n) is also determined for r is an element of {2,3, 4}.