The pessimistic diagnosability of bubble-sort star graphs and augmented k-ary n-cubes. Issue 3 (1st October 2016)

• Record Type: Journal Article
• Authors: Gu, Mei-Mei; Hao, Rong-Xia; Feng, Yan-Quan
• Is Part Of: International journal of computer mathematics. Volume 1:Issue 3/4(2016)
• Page Start: 98
• Page End: 112
• Publication Date: 2016-10-01
• Subjects: Pessimistic diagnosability -- PMC model -- bubble-sort star graph -- augmented k-ary n-cube -- interconnection network; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2016.1271015
• Languages: English
• ISSNs: 2379-9927

Abstract

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 .