Conditional Diagnosability Of The (n,k)-Arrangement Graphs And(n,k)-Star Graphs Under The PMC Model

In a multiprocessor system, the fault diagnosis process is the process of identifying the mistaken processors by testing each other, it plays a crucial role in guaranteeing the reliability of system, and is studied by many researchers. In1967, Preparata et al. proposed a model called PMC model, which pushed forward development of the fault diagnosis. Due to some defects in traditional diagnosable,in the work of Lai et al. in2005,they proposed a new measure for fault diagnosis of systems, that is, conditional diagnosability. In a same system, the diagnosibility is much more than traditional diagnosability. So the conditional fault diagnosability can better measure the diagnosable problem of a regular topological structure.In this brief, we research the conditional diagnosability of the (n,k)-arrangement graph An,k and (n, k)-star graph under the PMC model. The An,k graph and (n, k)-star graph, as the two variations of star graph, not only retain some favorable properties of star graph, for example:node and edge symmetric, maximal fault tolerance, simple shortest routing and hierarchical structure, but also provide more flexibility than the star graph in terms of choosing the major design parameters:degree, diameter and numbers of nodes. From the definition, we know that the (n,1)-arrangement graph An,1is isomorphic to (n,1)-star graph,and both are isomorphic to the complete graph. So there is no sense to research the two graph’s disagnosability. This paper get the conditional diagnosability of the (n,k)-arrangement graph An,k and (n, k)-star graph under the PMC model through mathematics.We use the symbol tc (G) to stand for the graph G’s conditional diagnosability.We get the conclusion that the conditional diagnosability of the (n,k)-arrangement graph An,k tc (An,k)=4(k-1)(n-k)-2for n≥5when k=2, n>7when k=3and4≤k≤n-2,and the conditional diagnosability of(n,k)-star graph tc(Sn,k)=n+3k-6when2<≤k≤n-3,and tc(Sn,n-2)=6n-17for n≥6.