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 $A{G}_n$ has many good properties. In this paper, we prove that the 3-extra diagnosability of $A{G}_n$ is $8n–25$ for $n\ge 5$ under the PMC model and for $n\ge 7$ MM* model.