Subnetwork preclusion for bubble-sort networks

• The fault tolerance of bubble-sort networks with respect to subnetwork preclusion was investigated.
• The (n−2)(n−2)-dimensional sub-bubble-sort network preclusion node (link) number was given.
• The result improved one of the main results in [Theor. Comput. Sci., 421 (2012) 62–69].

For two positive integers n and m   with n>mn>m, the Gn−mGn−m preclusion node (resp. link) number Fm(Gn)Fm(Gn) (resp. fm(Gn)fm(Gn)) of an n  -dimensional interconnection network GnGn is the minimum number of nodes (resp. links), if any, whose deletion results in a network with no subnetwork isomorphic to Gn−mGn−m. The n  -dimensional bubble-sort network BnBn is one of the most attractive interconnection networks for multiprocessor systems. In this paper, we prove that F2(Bn)=f2(Bn)=n(n−1)F2(Bn)=f2(Bn)=n(n−1) for n≥6n≥6.