Structure connectivity and substructure connectivity of bubble-sort star graph networks

The bubble-sort star graph, denoted BSn, is an interconnection network model for multiprocessor systems, which has attracted considerable interest since its first proposal in 1996 [5]. In this paper, we study the problem of structure/substructure connectivity in bubble- sort star networks. Two basic but important structures, namely path P-i and cycle C-i, are studied. Let T be a connected subgraph of graph G. The T-structure connectivity kappa(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to T. The T-substructure connectivity kappa(s)(G; T) of G is the cardinality of a minimum set of subgraphs in G, whose deletion disconnects G and every element in the set is isomorphic to a connected subgraph of T. Both T-structure connectivity and T-substructure connectivity are a generalization of the classic notion of node-connectivity. We will prove that for P2k+1, a path on odd nodes (resp. P-2k, a path on even nodes), kappa (BSn; P2k+1) = kappa(s)(BSn; P2k+1) = [2n-3/k+1] for n >= 4 and k +1 <= 2n - 3 (resp. kappa(BSn; P-2k) = kappa(s)(BSn; P-2k) = [2n-3/k] for n >= 5 and k <= 2n - 3). For a cycle on 2k nodes C-2k (there are only cycles on even nodes in BSn), kappa (BSn; C-2k) = kappa(s) (BSn, C-2k) = [2n-3/k] for n >= 5 and 2 <= k <= n -1. (C) 2019 Elsevier Inc. All rights reserved.