Fault diagnosability of Bicube networks under the PMC diagnostic model

Jiafei Liu, Shuming Zhou, Zhendong Gu, Qianru Zhou, Dajin Wang

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


A network's fault diagnosability is the maximum number of nodes (or processors) that are allowed to fail, while still being able to be identified by analyzing the syndrome of mutual testing, under the well-known PMC diagnostic model. It is a crucial indicator of the network's reliability. The original definition of diagnosability is often too strict to realistically reflect a network's robustness, because it is limited by the network's minimum degree. To better measure the actual reliability, many variants of diagnosability have been proposed, with g-extra diagnosability being one of the most noticeable diagnostic strategies. In this paper, we determine both the diagnosability and g-extra diagnosability for Bicube BQn, a recently proposed variant of the classic hypercube. We first show that the diagnosability for BQn, the n-dimensional Bicube, is n; and then prove that the g-extra diagnosability for BQn is (g+1)n−g−(g2).

Original languageEnglish
Pages (from-to)14-23
Number of pages10
JournalTheoretical Computer Science
StatePublished - 6 Jan 2021


  • Bicube
  • Connectivity
  • Diagnosability
  • Multiprocessor systems
  • PMC model


Dive into the research topics of 'Fault diagnosability of Bicube networks under the PMC diagnostic model'. Together they form a unique fingerprint.

Cite this