Conditional Diagnosability of the BC Networks under the Comparison Diagnosis Model*+

Abstract

An n-dimensional bijective connection network (BC network), denoted by Xn, is an n-regular graph with 2n vertices and n2n-1 edges. The n-dimensional hypercube, crossed cube, twisted cube, and Möbius cube are some examples of the n-dimensional BC networks. In [5], Lai et al. introduced a novel measure of diagnosability, called conditional diagnosability, by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. In this paper, we prove that the conditional diagnosability of Xn is 3(n-2)+1 under the comparison model, n≥5. As a corollary of this result, we obtain the conditional diagnosability of the hypercubes, crossed cubes, twisted cubes, and Möbius cubes.