Reliability of Complete Cubic Networks under the Condition ofg-Good-Neighbor
Xiangyang Xu, Shuming Zhou, Jinqiang Li · The Computer Journal · 2016
Fault tolerance is the ability such that a multiprocessor system operates properly in the event of the failure of some of its components. Latifi et al. [IEEE Trans. Comput. 43 (2) (1994) 218–222] proposed the notion of Rg-connectivity(κg) of a network modeled by graph G such that at least κg vertices in G should be deleted to disconnect the network, and the minimum degree of every connected component is at least g. This paper establishes κg(CCN(n))=(n−g+1)2g(1≤g≤n−2) for n-dimensional complete cubic network CCN(n). Fault diagnosability is another important metric for evaluating network reliability and availability. In 2012, Peng et al. [Appl. Math. Comput. 218 (21) (2012) 10406–10412] proposed a novel g-good-neighbor (conditional) diagnosability, which tacitly assumes that every fault-free vertex has at least g fault-free neighbors. In view of κg(CCN(n)), we show that the g-good-neighbor diagnosability of the complete cubic network CCN(n) under the PMC model (1≤g≤n−2) and the MM* model (1≤g≤n−2 and n≥4) is (n−g+2)2g−1, respectively.