Fault Tolerance of Bubble-sort Networks on Components

Reliability evaluation of interconnection networks are important to the design and maintenance of multiprocessor systems. The component connectivity is an important measure for the reliability of interconnection networks. The bubble-sort network Bn is a popular underlying topology for distributed systems. The t-component (edge) connectivity κ^t(G)(λ^t(G)) of a graph G=(V,E) is the minimum vertex (edge) number of a set F⊂V such that G−F is not connected and G–F has at least t components. In this paper, we determine the κ^t(Bn) and λ^t(Bn) for small t.