The G Good Neighbor Conditional Diagnosability Of Some Interconnection Networks

Alarge scale interconnection networksystem is modeled by a simple connected graph.The processors of the system are represented by the vertices in the graph and the connection between the processors is represented by the edge in the graph.With the increasing of the processor number in the system,it is a meaningful work to study the reliability of the system.Diagnosability is an important index to measure the reliability of the system.The classical diagnosability underestimates the fault diagnosis ability of the system.Lai et al.proposed the conditional diagnosability by restricting the neighbors of vertices of the system.Peng et al.proposed the g good neighbor conditional diagnosability,which restricts every fault-free node containing at least g fault-free neighbors.In this paper,we investigate the g good neighbor conditional diagnosability of(n,k)-arrangement graphs,balanced hypercubes and locally twisted cubes under the PMC model.We show the g good neighbor conditional diagnosability of(n,k)-arrangement graphs is[(g + 1)k-g](n-k)for k?g + 2,n?k + g,n ?5.The 1 good neighbor conditional diagnosability of balanced hypercubes is 4n-1 for n?2.The g good neighbor conditional diagnosability oflocally twisted cubes is 2g(n-g + 1)-1 for n?g + 3,n?3.We also show the g good neighbor conditional diagnosability of hierarchical cubic network under the MM*model is 2n + 1 and 4n-1 for g = 1,g = 2,respectively.