Reliability evaluation of complete cubic networks. Issue 1 (2nd January 2020) - Sun, Xueli; Zhou, Shuming; Gu, Zhendong; Wang, Yihong; Li, Min
Abstract : 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 ) ( C C N ( n ) ) = ( g + 1 ) n − g + 1 2 + 1 for n ≥ 2, 1 ≤ g ≤ n − 1, where C C N ( n ) is an n -dimensional complete cubic network, which generalises the hierarchical cubic network. Moreover, we establish t g ( C C N ( n ) ) = ( g + 1 ) ( n + 1 ) − g + 1 2 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 C C N ( n ) is [ ( k + 1 ) n − k + 1 2 + 1 ] / k -diagnosable under the PMC model. As a consequence, we also derive the related results of the n -dimensional hierarchical cubic network H C N n . GRAPHICAL ABSTRACT: