The 3-extra diagnosability of alternating group graphs

Abstract

The diagnosability of a multiprocessor system is one important study topic. In 2016, Zhang et al. proposed a new measure for fault diagnosis of the system, namely, the \( g \)-extra diagnosability, which restrains that every fault-free component has at least \( (g+1) \) fault-free nodes. As a favorable topology structure of interconnection networks, the \( n \)-dimensional alternating group graph \( AG_n \) has many good properties. In this paper, we prove that the 3-extra diagnosability of \( AG_n \) is \( 8n – 25 \) for \( n \geq 5 \) under the PMC model and for \( n \geq 7 \) MM* model.