The 2-good-neighbour diagnosability of modified bubble-sort graphs under the PMC and MM* model

摘要

The study of interconnection networks is a hot topic for multiprocessor systems. Diagnosability plays an important role in the study of interconnection networks. A new measure for fault diagnosis of a system is proposed by Peng et?al. in 2012. It is called g -good-neighbour diagnosability which restrains every fault-free vertex containing at least g fault-free neighbours. The n -dimensional modified bubble-sort graph M B n is a special Cayley graph. In this paper, we give that the 2-good-neighbour diagnosability of M B n under the PMC model is 4n ?5 for n ≥ 4 and the 2-good-neighbour diagnosability of M B n under the M M ? model is 4n ?5 for n ≥ 4 .