Diagnosability of the Cayley Graph Generated by Complete Graph with Missing Edges under the MM$^{* }$ Model. (14th November 2019) - Ren, Yunxia; Wang, Shiying
Abstract: 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 $CK_{n}$ has many good properties. In this paper, we study the local diagnosability of $CK_{n}$ and show it has the strong local diagnosability property even if there exist $(\frac{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.