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 · IEEE Transactions on Reliability · 2018
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.