The g-good neighbor conditional diagnosability of twisted hypercubes under the PMC and MM* model

摘要

Connectivity and diagnosability are important parameters in measuring the fault tolerance and reliability of interconnection networks. The g-good-neighbor conditional faulty set is a special faulty set that every fault-free vertex should have at least g fault-free neighbors. The Rg-vertex-connectivity of a connected graph G is the minimum cardinality of a g-good-neighbor conditional faulty set X⊆V(G) such that G−X is disconnected. The g-good-neighbor conditional diagnosability is a metric that can give the maximum cardinality of g-good-neighbor conditional faulty set that the system is guaranteed to identify. The twisted hypercube is a new variant of hypercubes with asymptotically optimal diameter introduced by X.D. Zhu. In this paper, we first determine the Rg-vertex-connectivity of twisted hypercubes, then establish the g-good neighbor conditional diagnosability of twisted hypercubes under the PMC model and MM* model, respectively.