Diagnosability of arrangement graphs with missing edges under the MM* model
Shiying Wang, Xiaolei Ma · International Journal of Parallel Emergent and Distributed Systems · 2019
Diagnosability is an important parameter to measure the fault tolerance of interconnection networks. Arrangement graph An,k is a generalisation of the star graphs, yet it is more flexible in its size than the star graphs. In this paper, we study the local diagnosability of An,k, and show that it has the strong local diagnosability property even if there exist (k−1)(n−k)−1 missing edges in it under the MM* model, and the result is optimal with respect to the number of missing edges.