The extra connectivity of bubble-sort star graphs

Connectivity plays an important role in measuring the fault tolerance of a multiprocessor system in the case of vertices failures. Extra connectivity is an important indicator of a network's ability for diagnosis and fault tolerance. In this paper, we analyze the fault tolerance ability of the bubble-sort star network, denoted by BSn, a well-known interconnection network proposed for multiprocessor systems, and establish the g-extra connectivity for 1≤g≤3.