Fault-tolerability of the hypercube and variants with faulty subcubes

A faulty vertex may probably affect its neighbors and further causes them being faulty, which makes a subnetwork (structure) fail. Therefore, looking into the effect caused by some structures becoming faulty is meaningful. The connectivity and diagnosability are two important parameters to evaluate the fault-tolerability of networks. The connectivity of a network is the minimum number of vertices whose removal will disconnect the network or trivial. We call the network to be t-diagnosable if the number of faulty vertices does not exceed t and all faulty vertices can be identified without a replacement. Let Q(n) be the n-dimensional hypercube and EH(s, t) be the exchanged hypercube, which is the variant of hypercube. In this paper, we study connectivity, diagnosability, and 1-good-neighbor conditional diagnosability based on structure faults, respectively. Specifically, we first determine the connectivity (1 <= k <= n - 1 and n >= 3) and diagnosability (1 <= k <= n - 1 and n >= 4) of Q(n) - Q(k) under the PMC model. Then, we determine the connectivity (2 <= k <= min{s, t}) and diagnosability (2 <= k <= min{s, t} and min{s, t} > 3) of EH(s, t) - Qk under the PMC model. Finally, we show that the 1-good-neighbor conditional diagnosability of Q(n) - Q(k) is 2n - 3 for n > 5 and 1 <= k <= n -1 under the PMC model, which is almost twice as the traditional diagnosability for a large n. (C) 2022 Elsevier Inc. All rights reserved.

Automated summary

The paper discusses the connectivity, diagnosability, and conditional diagnosability of networks based on structure faults, determining the minimum number of faulty vertices for network failure and identifying faulty vertices without replacement. Different models and variants of hypercubes are analyzed to evaluate fault-tolerability of networks, showing significant improvements in diagnosability under certain conditions.