Diagnosability Of Shuffle-cube And Bubble-sort Star Graphs

A multiprocessor system has an underlying topology,which is usually presented by a graph G,where nodes represent processors and links represent communication links between processors.In 2012,Peng et al.proposed the g-good-neighbor diagnosability of G that restrains each fault-free vertex containing at least g fault-free neighbors.The n-dimensional shuffle-cube SQn is a vaxiation of the hypercube.In this paper,we show that the 1-good-neighbor diagnosability of SQn under the PMC model and MM*model is 2n-3 for n≥ 6.The bubble-sort star graph BSn has many good properties.In this paper,we show that BSn has the strong local diagnosability under the MM*model and prove that BSn keeps this strong property even if there exist(2n-5)missing edges in it,and the result is optimal with respect to the number of missing edgesThe following is the main content of this paper:In the first chapter,we briefly introduce the research background and research status,some concepts of graph theory,and two famous fault diagnosis models,i.e.,the PMC model and MM*model.In the second chapter,we briefly introduce the definitions of shuffle-cube SQn and prove that the 1-good-neighbor diagnosability of shuffle-cube SQn is 2n-3 for n≥ 6 under the PMC model and the MM*modelIn the third chapter,we briefly introduce the definitions of bubble-sort star graph BSn,and prove that the bubble-sort star graph BSn keeps the strong local diagnosability under the comparison model,and it keeps this strong property even if there exist 2n-5 missing edges in it,and the result is optimal with respect to the number of missing edges.