The pessimistic diagnosability of bubble-sort star graphs and augmented k-ary n-cubes

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 .

KEYWORDS:

• Pessimistic diagnosability
• PMC model
• bubble-sort star graph
• augmented k-ary n-cube
• interconnection network

Acknowledgments

The authors express their sincere thanks to the editor and the anonymous referees for their valuable suggestions which greatly improved the original manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China (Nos. 11371052, 11571035, 11271012), the Fundamental Research Funds for the Central Universities (Nos. 2016JBM071, 2016JBZ012) and the 111 Project of China (B16002).