Subnetwork preclusion for bubble-sort networks

摘要

For two positive integers n and m with n > m, the G(n-m) preclusion node (resp. link) number F-m(G(n)) (resp. f(m)(G(n))) of an n-dimensional interconnection network G(n) is the minimum number of nodes (resp. links), if any, whose deletion results in a network with no subnetwork isomorphic to G(n-m). The n-dimensional bubble-sort network B-n is one of the most attractive interconnection networks for multiprocessor systems. In this paper, we prove that F-2(B-n) = f(2)(B-n) = n(n-1) for n >= 6. (C) 2015 Elsevier B.V. All rights reserved.