The Relationship between g-Restricted Connectivity and g-Good-Neighbor Fault Diagnosability of General Regular Networks

Limei Lin, Sun Yuan Hsieh, Riqing Chen, Li Xu, Chia Wei Lee

Research output: Contribution to journalArticlepeer-review

46 Citations (Scopus)


The g-restricted connectivity (g-RC) is the minimum vertex-set size of a network, whose deletion disconnects the network such that each remaining vertex has at least g neighbors in its respective component. The g-RC is a deterministic indicator of tolerability of a network with failing processors. The g-good-neighbor fault diagnosability (g-GNFD) is the largest set size of correctly identified faulty vertices in a network such that any good vertex has no fewer g good neighbors. This paper establishes the relationship between g-RC and g-GNFD of general regular networks, first under the PMC model and second under the MM∗ model. Moreover, this paper directly gives the g-GNFD of some well-known special networks by their g-RC and our proposed relationship.

Original languageEnglish
Pages (from-to)285-296
Number of pages12
JournalIEEE Transactions on Reliability
Issue number1
Publication statusPublished - 2018 Mar

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering

Cite this