Reliability evaluation of complete cubic networks
Xueli Sun, Shuming Zhou, Zhendong Gu, Yihong Wang, Min Li · International Journal of Parallel Emergent and Distributed Systems · 2019
Fault diagnostic analysis is extremely important for interconnection networks. Given a graph G and a positive integer g, the g-extra connectivity of G (denoted by κo(g)(G)) is the minimum cardinality of a subset S of V(G) such that G−S is disconnected and every remaining component has at least g + 1 vertices. The g-extra diagnosability of G (denoted by t~g(G)), is the maximum number of faulty vertices that the system can guarantee to identify under the condition that every fault-free component contains at least g + 1 vertices. The t/k-diagnosis strategy can detect up to t faulty vertices which might include at most k misdiagnosed vertices. In this paper, we first determine κo(g)(CCN(n))=(g+1)n−g+12+1 for n≥ 2, 1≤g≤ n−1, where CCN(n) is an n-dimensional complete cubic network, which generalises the hierarchical cubic network. Moreover, we establish t~g(CCN(n))=(g+1)(n+1)−g+12 under the PMC model (n≥ 4, 1≤g≤ n−3) and under the MM* model (n≥ 6, 1≤g≤(n−2)/4), respectively. Furthermore, we show that CCN(n) is [(k+1)n−k+12+1]/k-diagnosable under the PMC model. As a consequence, we also derive the related results of the n-dimensional hierarchical cubic network HCNn.