The Nature Diagnosability of Bubble-sort Star Graphs under the PMC Model and MM Model

Mujiangshan Wang, Yuqing Lin, Shiying Wang

Many multiprocessor systems have interconnection networks as underlying topologies and an interconnection network is usually represented by a graph where nodes represent processors and links represent communication links between processors. No fault set can contain all the neighbors of any fault-free vertex in the system, which is called the nature diagnosability of the system. Diagnosability of a multiprocessor system is one important study topic. As a famous topology structure of interconnection networks, the -dimensional  bubble-sort star graph  has many good properties. In this paper, we prove that the nature diagnosability of  is  under the PMC model for , the nature diagnosability of  is  under the MM model for .