Diagnosability of arrangement graphs with missing edges under the MM* model

Abstract

Diagnosability is an important parameter to measure the fault tolerance of interconnection networks. Arrangement graph $A_{n,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 $A_{n,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.

GRAPHICAL ABSTRACT

Keywords:

• Interconnection network
• Local diagnosability
• MM* model
• arrangement graph

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by the National Natural Science Foundation of China (61772010) and the Science Foundation of Henan Normal University [Xiao 20180529, 20180454 and 5201019120307].