Mass data processing and complex problem solving have higher and higher demands for performance of multiprocessor systems. Many multiprocessor systems have interconnection networks as underlying topologies. The interconnection network determines the performance of a multiprocessor system. In the system where the processors and their communication links to each other are likely to fail, it is important to consider the fault tolerance of the network. At this background, the strong connectivity of the network is proposed. For the strong connectivity, it allows both processors and communication links to fail at the same time. For the traditional connectivity, the connectivity only allows processors failure and the edge connectivity only allows communication link failure. In the design of an interconnection network, one of the most fundamental considerations is the connectivity of the network. In this paper, we give the definition of the strong connectivity of the network and some properties of the strong connectivity of the network. As a favorable topology structure of interconnection networks, the n-dimensional bubble-sort star graph BSn has many good properties. We give some strong connectivity of BSn⁠, too.

Connectivity plays an important role in measuring the fault tolerance of interconnection networks G=(V,E)⁠. A faulty set F⊆V is called a g-extra faulty set if every component of G−F has more than g nodes. A g-extra cut of G is a g-extra faulty set F such that G−F is disconnected. The minimum cardinality of g-extra cuts is said to be the g-extra connectivity of G. Diagnosability is an important metric for measuring the reliability of G. A new measure for fault diagnosis of G restrains that every fault-free component has at least (g+1) fault-free nodes, which is called the g-extra diagnosability of G. As a favorable topology structure of interconnection networks, the n-dimensional bubble-sort star graph BSn has many good properties. In this paper, we prove that 2-extra connectivity of BSn is 6n−15 for n≥5 and the 2-extra connectivity of BS4 is 8; the 2-extra diagnosability of BSn is 6n−13 under the PMC model for n≥5 and the 2-extra diagnosability of BSn is 6n−13 under the MM* model for n≥6⁠.