Diagnosability of the Cayley Graph Generated by Complete Graph with Missing Edges under the MM* Model

Diagnosability of a multiprocessor system is an important research topic. The system and an interconnection network have an underlying topology, which is usually presented by a graph. Under the Maeng and Malek's (MM) model, to diagnose the system, a node sends the same task to two of its neighbors, and then compares their responses. The MM* is a special case of the MM model and each node must test all pairs of its adjacent nodes. In 2009, Chiang and Tan (Using node diagnosability to determine t-diagnosability under the comparison diagnosis (cd) model. IEEE Trans. Comput., 58, 251-259) proposed a new viewpoint for fault diagnosis of the system, namely, the node diagnosability. As a new topology structure of interconnection networks, the nest graph CKn has many good properties. In this paper, we study the local diagnosability of CKn and show it has the strong local diagnosability property even if there exist (n(n-1)/2 - 2) missing edges in it under the MM* model, and the result is optimal with respect to the number of missing edges.