2017/01/29 by Mei-Mei Gu, Gu, Mei-Mei, Rong‐Xia Hao +5
Computer Science · Engineering · #68R10 #Biofuel production and bioconversion #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1701.08355
openalex publication_date 2017/01/29 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
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.