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 tgPMC(G) and tgMM*(G), respectively. In this paper, we first determine that tgPMC(G)=tgMM*(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 R2-connectivities of BC graphs and folded hypercubes.