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

Abstract

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 $MB_{n} $ is a special Cayley graph. In this paper, we give that the 2-good-neighbour diagnosability of $MB_{n} $ under the PMC model is 4n−5 for $n\geq 4 $ and the 2-good-neighbour diagnosability of $MB_{n} $ under the $MM^{*} $ model is 4n−5 for $n\geq 4 $.

Keywords

• interconnection network
• diagnosability
• modified bubble-sort graph
• 2-good-neighbour