摘要 : 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 processor mistaken as a faulty one. The pes... 展开 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 processor mistaken as a faulty one. The pessimistic diagnosability of a system G, denoted by t(p)(G), is the maximal number of faulty processors so that the system G is t/t-diagnosable. The pessimistic diagnosability of alternating group graphs AG(n) (Tsai, 2015); BC networks (Fan, 2005; Tsai, 2013); the k-ary n-cube networks Q(n)(k), (Wang et al., 2012); regular graphs including the alternating group networks AN(n) (Hao et al., 2016) etc. But most of these results are about networks G with cn(G) <= 2 (where cn(G) is the maximum number of common neighbors for any two distinct vertices). In this paper, we study the pessimistic diagnosability of three kinds of graphs which are (n, k)-arrangement graphs A(n,k), (n, k) - star graphs S-n,S-k and balanced hypercubes BHn, where cn(A(n,k)) = cn(S-n,S-k) = n - k - 1 and cn(BHn) = 2n. We proved that t(p)(A(n,k)) = (2k - 1)(n - k) - 1 for n >= k + 2 and k >= 3, t(p)(S-n,S-k) = n + k - 3 for n >= k + 2 and k >= 3, and t(p)(BHn) = 2n for n >= 2. As corollaries, the pessimistic diagnosability of the known results about AG(n) and AN(n) is obtained directly. (C) 2016 Elsevier B.V. All rights reserved. 收起