The fault tolerance of (n, k)-bubble-sort networks

The h-good neighbor connectivity k(h)(G) is an important parameter to evaluate the fault tolerance of an interconnection network G. So far, almost all known results of k(h)(G) are about small h's except the hypercubes, the star graphs, the k-ary n-cubes and hierarchical hypercube network HHCn et al. In this paper, we focus on k(h)(B-n,B-k) for the (n, k)-bubble-sort network B-n(,k), which is a generalization of the bubble-sort graph B-n as it is a special case of (n, k)-bubble-sort networks for k = n1. We show that k(h)(B-n,B-k) = n+h(k-2) - 1 for 2 <= k <= inverted right perpendicular n+3/2 inverted left perpendicular and o <= h <= left perpendicular n-3/2 right perpendicular, which implies that at least n + h(k - 2) - 1 vertices of B-n,B-k have to be deleted to get a disconnected graph without vertices of degree less than h. (C) 2020 Elsevier B.V. All rights reserved.