Fault-tolerant of Bubble-sort Star Graph Based on Subgraph Fault Pattern

Connectivity is an important metric for fault tolerance in interconnection networks. Menger’s theorem reveals the relationship between connectivity and disjoint paths in a graph. Disjoint paths not only avoid communication bottlenecks, but also provide alternative paths in case of vertex failures. Let [Formula: see text] [Formula: see text] be a [Formula: see text]-dimensional sub-bubble-sort star of [Formula: see text]. In this paper, we show that [Formula: see text] is strongly Menger (edge) connected. Later, we show that the connectivity and edge-connectivity of [Formula: see text] are uniformly [Formula: see text]. In addition, we show that the 1-extra connectivity of [Formula: see text] is [Formula: see text] for [Formula: see text].