Conditional diagnosability of bubble-sort star graphs

Diagnosability plays an important role in measuring the reliability of interconnection networks. Conditional faulty set is a special faulty set that does not contain all of neighbors of any vertex in a network. The conditional diagnosability is a metric that can give the maximum cardinality of the conditional faulty sets that the system is guaranteed to identify. This paper shows that the conditional diagnosability of the bubble-sort star graph BSnBSn under the MM model is 6n−156n−15 for n≥6n≥6 and under the PMC model is 8n−218n−21 for n≥5n≥5.