The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks

Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system´s ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3, and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AG_n, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AG_n´s traditional diagnosability. As a byproduct, the strong diagnosability of AG_n is also obtained.