The pessimistic diagnosability of three kinds of graphs

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 tp(G), is the maximal number of faulty processors so that the system G is t/t-diagnosable. The pessimistic diagnosability of alternating group graphs AGn (Tsai, 2015); BC networks (Fan, 2005; Tsai, 2013); the k-ary n-cube networks Qnk, (Wang et al., 2012); regular graphs including the alternating group networks ANn (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 An,k, (n,k)-star graphs Sn,k and balanced hypercubes BHn, where cn(An,k)=cn(Sn,k)=n−k−1 and cn(BHn)=2n. We proved that tp(An,k)=(2k−1)(n−k)−1 for n≥k+2 and k≥3, tp(Sn,k)=n+k−3 for n≥k+2 and k≥3, and tp(BHn)=2n for n≥2. As corollaries, the pessimistic diagnosability of the known results about AGn and ANn is obtained directly.