The Nature Diagnosability of Bubble-sort Star Graphs under the PMC Model and MM Model
Mujiangshan Wang, Yuqing Lin, Shiying Wang · NOVA (University of Newcastle Australia) · 2017
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 n-dimensional bubble-sort star graph BSn has many good properties. In this paper, we prove that the nature diagnosability of BSn is 4n - 7 under the PMC model for n ≥ 4, the nature diagnosability of BSn is n ≥ 4 under the MM* model for n ≥ 5 .