The pessimistic diagnosabilities of some general regular graphs

The pessimistic diagnosis strategy is a classic strategy based on the PMC model. A system is t/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistaken as a faulty one. The pessimistic diagnosability of a system G, denoted by tp(G), is the maximal number of faulty processors so that the system G is t/t-diagnosable. In this paper, we study the pessimistic diagnosabilities of some general k-regular k-connected graphs Gn. The main result tp(Gn)=2k−2−g under some conditions is obtained, where g is the maximum number of common neighbors between any two adjacent vertices in Gn. As applications of the main result, every pessimistic diagnosability of many famous networks including some known results, such as the alternating group networks ANn, the k-ary n-cubes Qnk, the star graphs Sn, the matching composition networks G(G1,G2;M) and the alternating group graphs AGn, are obtained.