On g-Extra Conditional Diagnosability of Twisted Hypercubes under MM* Model

摘要

Connectivity and diagnosability are important parameters in measuring the reliability and fault-tolerance of an interconnection network G. The g-extra conditional faulty set F is a faulty vertex set such that every component of G - F has at least g + 1 vertices. The g-extra connectivity kappa(g) (G) of a connected graph G is the minimum cardinality of a g-extra conditional faulty set F of G such that G - F is disconnected. The g-extra conditional diagnosability t(g) (G) of a graph G is the maximum value of t such that G is g-extra conditionally t-diagnosable. The g-extra connectivity of G is necessary for g-extra diagnosability of G. The n-dimensional twisted hypercube H-n is a new variant of hypercubes with asymptotically optimal diameter. In this paper, we first give the g-extra connectivity of H-n for n >= 4 and 0 <= g <= n - 3; and then obtain the g-extra conditional diagnosability of H-n for n >= 5 and 0 <= g <= n-1/4 under the MM* model.