The 1-good-neighbor connectivity and diagnosability of Cayley graphs generated by complete graphs

Diagnosability is a significant metric to measure the reliability of multiprocessor systems. In 2012, a new measure for fault tolerance of the system was proposed by Peng et al. This measure is called the g-good-neighbor diagnosability that restrains every fault-free node to contain at least g fault-free neighbors. The Cayley graph CKn generated by the complete graph Kn has many good properties as other Cayley graphs. In this paper, we show that the connectivity of CKn is n(n−1)2, the 1-good-neighbor connectivity of CKn is n2−n−2 and the 1-good-neighbor diagnosability of CKn under the PMC model is n2−n−1 for n≥4 and under the MM∗ model is n2−n−1 for n≥5.