Ji Jirimutu and Shiying Wang Pages 108 - 115 ( 8 )
Background: Many multiprocessor systems have interconnection networks as underlying topologies, also described in various patents, and an interconnection network is usually represented by a graph where nodes represent processors and links represent communication links between processors. For the system, study of the topological properties of its interconnection network is important. In 2012, Peng et al. proposed a new measure for fault diagnosis of the system, namely, the g-goodneighbor diagnosability (which is also called the g-good-neighbor conditional diagnosability), which requires that every fault-free node contains at least g fault-free neighbors. The n-dimensional alternating group graph network ANn has been proved to be an important viable candidate for interconnecting a multiprocessor system. The feature of ANn includes low degree of node, small diameter, symmetry, and high degree of fault-tolerance.Results: In this paper, we prove that the 1-good-neighbor diagnosability (which is also called the nature diagnosability) of ANn is 2n-4 for n >5 under the PMC model and MM* model, the nature diagnosability of 4-dimensional alternating group graph network AN4 under the PMC is 4 and the nature diagnosability of AN4 under the MM* model is 3. Conclusion: In this paper, we investigate the problem of the nature diagnosability of AN4 under the PMC model and MM* model. It is proved that the nature diagnosability of ANn under the PMC model and MM* model is 2n-4 when n >5. The above results show that the nature diagnosability is several times larger than the classical diagnosability of ANn depending on the condition: 1-good-neighbors. The work will help engineers to develop more different measures of the nature diagnosability based on application environment, network topology, network reliability, and statistics related to fault patterns.
Interconnection network, graph, diagnosability, alternating group graph network, PMC model, MM* model.
Institute of Discrete Mathematics, College of Mathematics, Inner Mongolia University for Nationalities, Tongliao 028043, School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan