Relating Extra Connectivity and Extra Conditional Diagnosability in Regular Networks

Limei Lin, Li Xu, Riqing Chen, Sun Yuan Hsieh, Dajin Wang

Research output: Contribution to journalArticlepeer-review

63 Scopus citations


The h-extra node-connectivity of a graph G is the size of a minimal node-set, whose removal will disconnect G, but each remaining component has no fewer h+1 nodes. Based on h-extra node-connectivity, the h-extra conditional fault-diagnosability of networks has been proposed for a better, more realistic measure of networks' fault-tolerability. It is the maximal x such that G is h-extra conditionally x-fault-diagnosable. This paper will establish a relationship between the h-extra node-connectivity and h-extra conditional fault-diagnosability for a regular graph G, under the classic PMC diagnostic model. We will apply the newly found relationship to a variety of well-known regular networks, to directly obtain their h-extra conditional fault-diagnosability. The significance of the paper's work is that it relates the notions of h-extra node-connectivity and h-extra conditional fault-diagnosability, so that a regular network's h-extra conditional fault-diagnosability may be known once its h-extra node-connectivity is known.

Original languageEnglish
Article number7979592
Pages (from-to)1086-1097
Number of pages12
JournalIEEE Transactions on Dependable and Secure Computing
Issue number6
StatePublished - 1 Nov 2019


  • Extra conditional fault-diagnosability
  • PMC model
  • extra node-connectivity
  • fault diagnosis
  • general regular graphs


Dive into the research topics of 'Relating Extra Connectivity and Extra Conditional Diagnosability in Regular Networks'. Together they form a unique fingerprint.

Cite this