The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks
Shiying Wang, Zhenhua Wang, Mujiangshan Wang · The Computer Journal · 2016
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.