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

Abstract

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 $t_p(G)$ equals the extra connectivity ${\kappa }_1(G)$ of a regular graph $G$ under some conditions are shown. Furthermore, the following new results are gotten: the pessimistic diagnosability $t_p(S_n^2)=4n-9$ for split-star networks $S_n^2$, $t_p({\Gamma }_n)=2n-4$ for Cayley graphs generated by transposition trees ${\Gamma }_n$, $t_p({\Gamma }_n(\Delta ))=4n-11$ for Cayley graph generated by the $2$-tree ${\Gamma }_n(\Delta )$, $t_p(B{P}_n)=2n-2$ for the burnt pancake networks $B{P}_n$. 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.

23 pages