Fault tolerance in bubble-sort graph networks

The bubble-sort graph Bn is one of the attractive underlying topologies for distributed systems. FB(n,k) (resp. fB(n,k)) is the minimum number of faulty nodes (resp. links) that make every (n−k)-dimensional sub-bubble-sort graph faulty in Bn under node (resp. link) failure model. In this paper, we proved that FB(n,0)=fB(n,0)=1, FB(n,1)=fB(n,1)=n for n≥4, FB(n,2)≤fB(n,2)≤n(2n−3) for n≥6, FB(n,n−2)=n!/2 for n≥3, fB(n,n−2)=(n−1)n!/2 for n≥3, FB(n,n−1)=n! for n≥2, and for n≥6 and 3≤k≤n−3.