Diagnosability of Bubble-Sort Star Graphs with Missing Edges

摘要

The diagnosability of a multiprocessor system plays an important role. The bubble-sort star graph BS_n has many good properties. In this paper, we study the diagnosis on BS_n 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 BS_n (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.