Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs

Extra connectivity and the pessimistic diagnosis are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processor. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty vertices within a set containing at most one fault-free vertex. In this paper, the result that the pessimistic diagnosability tp(G) equals the extra connectivity κ1(G) of a regular graph G under some conditions are shown. Furthermore, the following new results are gotten: the pessimistic diagnosability tp(Sn2)=4n−9 for split-star networks Sn2; tp(Γn)=2n−4 for Cayley graphs generated by transposition trees Γn; tp(Γn(Δ))=4n−11 for Cayley graph generated by the 2-tree Γn(Δ); tp(BPn)=2n−2 for the burnt pancake networks BPn. As corollaries, the known results about the extra connectivity and the pessimistic diagnosability of many famous networks including the alternating group graphs, the alternating group networks, BC networks, the k-ary n-cube networks etc. are obtained directly.