Fault-tolerant maximal local-connectivity on Bubble-sort star graphs

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processor and communication links, respectively. Connectivity is an important measurement for the fault tolerant in interconnection network. Two vertices is maximally local-connected if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. In this paper, we show that an nn-dimensional Bubble-sort star graph is (2n−5)(2n−5)-fault-tolerant maximally local-connected and is also (2n−6)(2n−6)-fault-tolerant one-to-many maximally local-connected.