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.
No takes yet. Share an insight, caveat, or question.
Wang et al. (2016) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: