The 1, 2-good-neighbor conditional diagnosabilities of regular graphs.

Fault diagnosis of systems is an important area of study in the design and maintenance of multiprocessor systems. In 2012, Peng et al. proposed a new measure for the fault diagnosis of systems, namely g -good-neighbor conditional diagnosability, which requires that any fault-free vertex has at least g fault-free neighbors in the system. The g -good-neighbor conditional diagnosabilities of a graph G under the PMC model and the MM* model are denoted by t g PMC ( G ) and t g MM * ( G ) , respectively. In this paper, we first determine that t g PMC ( G ) = t g MM * ( G ) if g  ≥ 2. Second, we establish a general result on the 1, 2-good-neighbor conditional diagnosabilities of some regular graphs. As applications, the 1, 2-good-neighbor conditional diagnosabilities of BC graphs, folded hypercubes and four classes of Cayley graphs, namely unicyclic-transposition graphs, wheel-transposition graphs, complete-transposition graphs and tree-transposition graphs, are determined under the PMC model and the MM* model. In addition, we determine the R 2 -connectivities of BC graphs and folded hypercubes. [ABSTRACT FROM AUTHOR]