Diagnosability of Bubble-Sort Star Graphs with Missing Edges
Shiying Wang, Yingying Wang · Journal of Interconnection Networks · 2019
The diagnosability of a multiprocessor system plays an important role. The bubble-sort star graph BSn has many good properties. In this paper, we study the diagnosis on BSn under the comparison model. Following the concept of the local diagnosability, the strong local diagnosability property is discussed. This property describes the equivalence of the local diagnosability of a node and its degree. We prove that BSn (n ≥ 5) has this property, and it keeps this strong property even if there exist (2n − 5) missing edges in it, and the result is optimal with respect to the number of missing edges.