## Abstract

The bubble-sort star graph, denoted BS_{n}, 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 κ(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 κ^{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 P_{2k+1}, a path on odd nodes (resp. P_{2k}, a path on even nodes), [Formula presented] for n ≥ 4 and k+1≤2n−3 (resp. [Formula presented] for n ≥ 5 and k≤2n−3). For a cycle on 2k nodes C_{2k} (there are only cycles on even nodes in BS_{n}), κ(BS_{n};C_{2k})=κ^{s}(BS_{n};C_{2k})=⌈[Formula presented] for n ≥ 5 and 2≤k≤n−1.

Original language | English |
---|---|

Article number | 124632 |

Journal | Applied Mathematics and Computation |

Volume | 363 |

DOIs | |

State | Published - 15 Dec 2019 |

## Keywords

- Bubble-sort star graphs
- Cycles
- Interconnection networks
- Paths
- Structure connectivity
- Substructure connectivity