The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks

Connectivity plays an important role in measuring the fault tolerance of interconnection networks G = (V, E). A faulty set F subset of 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.