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

Mei-Mei Gu, Rong-Xia Hao, Jun-Ming Xu, Yan-Quan Feng

Published 2017-01-29Version 1

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}(BP_n)=2n-2$ for the burnt pancake networks $BP_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.