Path and cycle fault tolerance of bubble-sort graph networks.

The bubble-sort graph B n is one of attractive underlying topologies for distributed systems. Let H be a certain connected subgraph of B n. The H -structure connectivity of B n , denoted κ (B n ; H) , is the cardinality of a minimal set of subgraphs F = { H 1 , H 2 , ... , H m } in B n , such that every H i ∈ F is isomorphic to H , and F 's removal will disconnect B n. The H -substructure connectivity of B n , denoted κ s (B n ; H) , is the cardinality of a minimal set of subgraphs F = { J 1 , J 2 , ... , J m } , such that every J i ∈ F is isomorphic to a connected subgraph of H , and F 's removal will disconnect B n. The two kinds of connectivity are both generalizations of the classic connectivity. In this paper, we prove that κ (B n ; P k) = κ s (B n ; P k) = ⌈ 2 (n − 1) k + 1 ⌉ for n ≥ 6 and odd k ≤ 2 n − 3 , κ (B n ; P k) = κ s (B n ; P k) = ⌈ 2 (n − 1) k ⌉ for n ≥ 6 and even k ≤ 2 n − 2 , and κ (B n ; C 2 k) = κ s (B n ; C 2 k) = ⌈ n − 1 k ⌉ for 6 ≤ 2 k ≤ n − 1. [ABSTRACT FROM AUTHOR]