Fault tolerance in bubble-sort graph networks

The bubble-sort graph B-n is one of the attractive underlying topologies for distributed systems. F-B(n, k) (resp. f(B)(n, k)) is the minimum number of faulty nodes (resp. links) that make every (n - k)-dimensional sub-bubble-sort graph faulty in B, under node (resp. link) failure model. In this paper, we proved that F-B(n, 0) = f(B)(n, 0) = 1, F-B(n, 1) = f(B)(n, 1) = n for n >= 4, F-B(n, 2) <= f(B)(n, 2) <= n(2n - 3) for n >= 6, F-B(n, n - 2) = n!/2 for n >= 3, f(B)(n, n - 2) = (n - 1)n!/2 for n >= 3, F-B(n, n - 1) = n! for n >= 2, and F-B(n, k) <= f(B)(n, k) <= inverted right perpendicular(k+ 1)/2inverted left perpendiculark!C-k(n) for n >= 6 and 3 <= k <= n - 3. (C) 2011 Elsevier B.V. All rights reserved.