The pessimistic diagnosability of bubble-sort star graphs and augmented k-ary n-cubes. Issue 3 (1st October 2016) - Gu, Mei-Mei; Hao, Rong-Xia; Feng, Yan-Quan
ABSTRACT: 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, is the maximal number of faulty processors so that the system G is t / t -diagnosable. The known results about for alternating group graphs [Inform. Process. Lett. (2015), pp. 151–154]; BC networks [IEEE Trans. Comput. (2005), pp. 176–184]; the k -ary n -cube networks [IEEE Trans. Comput. (1991), pp. 232–237], [Int. J. Comput. Math. (2012), pp. 1–10] etc. have property that . In this paper, we study the pessimistic diagnosability of two kinds of graphs with, those are: bubble-sort star graphs and augmented k -ary n -cubes, and prove that for, for, and for and .