Conditional diagnosability of multiprocessor systems based on Cayley graphs generated by transpositions

Abstract Let Γ n be the symmetric group on { 1 , 2 , … , n } and S be the generating set of Γ n . The corresponding Cayley graph is denoted by Γ n ( S ) . If all elements of S are transpositions, a simple way to depict S is to via a graph, called the transposition generating graph of S , denoted by A ( S ) (or say simply A ), where the vertex set of A is { 1 , 2 , … , n } , there is an edge in A between i and j if and only if the transposition ( i j ) ∈ S , and Γ n ( S ) is called a Cayley graph obtained from a transposition generating graph A . Conditional diagnosability, proposed by Lai et al, is a novel measure of diagnosability that adds the additional condition that any faulty set cannot contain all of the neighbors of any vertex in a system. There are two well-known diagnostic models, PMC model and MM* model. The conditional diagnosability under the PMC (resp. MM*) model of a graph G , denoted by t c P M C ( G ) (resp. t c M M ∗ ( G ) ), is the maximum value of t is the maximum value of t such that G is conditionally t -diagnosable under the PMC (resp. MM*) model. The conditional diagnosability of many well-known multiprocessor systems has been explored. In this paper, by exploring the structural properties of these Cayley graphs, suppose | E ( A ) | is the number of edges in the transposition generating graph A , we obtain the following results: (1) Under the MM* model, t c M M ∗ ( Γ n ( S ) ) = 3 | E ( A ) | − 6 , if  A  has a triangle; 3 | E ( A ) | − 5 , if  A  has no triangles and  A  is not a star. (2) Under the PMC model, t c P M C ( Γ n ( S ) ) = 4 | E ( A ) | − 9 , if  A  has a triangle; 4 | E ( A ) | − 7 , if  A  has no triangles and  A  is not a star. As corollaries, the conditional diagnosability of many kinds of graphs under the MM* model and the PMC model such as Cayley graphs generated by unicyclic graphs, wheel graphs, complete graphs, tree graphs etc. are obtained.