Conditional Diagnosability of Matching Composition Networks Under the PMC Model

Abstract

In the work of Lai in 2005, they proposed a new measure for fault diagnosis of systems, namely, <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">conditional diagnosability</i> . It assumes that no fault set can contain all the neighbors of any vertex in the system. In the same paper, they showed that the conditional diagnosability of hypercube <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Qn</i> is 4( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> - 2) + 1 for <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ges 5. In this brief, we generalize this result by considering a family of more popular networks, namely, matching composition networks (MCNs), which are a class of networks composed of two components of the same order linked by a perfect matching under PMC (Preparata, Metze and Chien) model. We determine in Theorem 7 the conditional diagnosability for some MCNs, from which we deduce that the hypercube <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Qn</i> , the crossed cube CQ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> , the twisted cube TQ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> , and the MOumlbius cube MQ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> all have the same conditional diagnosability of 4( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> - 2) + 1 for <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> ges 5. We show that the bijective connection (BC) networks in the work of Fan and He in 2003 and the work of Zhu in 2008 satisfy the conditions of Theorem 7, and thus, our conditional diagnosability result also applies to BC networks. Finally, we show that the MCNs satisfying the conditions of Theorem 7 are more general than the BC networks.