The 1-Good-Neighbor Conditional Diagnosability of Some Regular Graphs

The g-good-neighbor conditional diagnosability is the maximum number of faulty vertices a network can guarantee to identify, under the condition that every fault-free vertex has o at least g fault-free neighbors. In this paper, we study the 1-good-neighbor conditional diagnosabilities of some general k-regular k-connected graphs G under the PMC model and the MM* model. The main result t(1)(G) = 2k-l-1 under some conditions is obtained, where is the maximum number of common neighbors between any two adjacent vertices in G. Moreover, the following results are derived: t(1)(HSn)= 2n - 1 for the hierarchical star networks, t(1)(X-n) = 2n-1 for the BC networks, t(1)(AG(n)) = 4n-10 for the alternating group graphs AG(n).