The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model
Mujiangshan Wang, Yubao Guo, Shiying Wang · International Journal of Computer Mathematics · 2015
Diagnosability is an important metric for measuring the reliability of multiprocessor systems. In 2012, Peng et al. proposed a new measure for fault tolerance of the system, which is called g-good-neighbour diagnosability that restrains every fault-free node containing at least g fault-free neighbours. As a favourable topology structure of interconnection networks, the Cayley graph CΓn generated by the transposition tree Γn has many good properties. In this paper, we give that the 1-good-neighbour diagnosability of CΓn under the PMC model and MM∗ model is 2n−3 except the bubble-sort graph B4 under MM∗ model, where n≥4, and the 1-good-neighbour diagnosability of B4 under the MM∗ model is 4.