The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model

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 Gamma(n) generated by the transposition tree Gamma(n) has many good properties. In this paper, we give that the 1-good-neighbour diagnosability of C Gamma(n) under the PMC model and MM* model is 2n -3 except the bubblesort graph B4 under MM* model, where n = 4, and the 1-good-neighbour diagnosability of B-4 under the MM* model is 4.