Diagnosability Of Hypercubes And Folded Hypercubes

The diagnosability of multiprocessors plays an irreplaceable role in studying the reliability and faulty tolerance of interconnection networks.Hypercubes and folded hypercubes are two kinds of internet networks widely studied because of their good properties.The internet is composed of multiprocessor systems,which can be simplified into a form of graph.Processors can be represented by vertices in the graph,and the communication links between processors can be represented by edges between vertices.The n-dimensional hypercube can be expressed by Qn.Its vertex set is V(Qn)={u1u2…un-1un|uk∈{0,1},1≤k≤n},and any two vertices are adjacent if and only if only one position of the two vertices is different.The n-dimensional folded hypercube can be expressed by FQn.Its vertex set is same as Qn,and any two vertices are adjacent if and only if only one position of the two vertices is different or all positions are different.The n-dimensional folded hypercube FQn has 2n-1 more edges than the n-dimensional hypercube Qn.Scholars have put forward many models when studying the problem of system faulty diagnosis,among which the two commonly used models are MM*model and PMC model.Let F be the set of faulty edges.In this paper,we mainly study the diagnosability of hypercubes and folded hypercubes with faulty edges under the MM*model.And we also study the diagnosability of folded hypercubes with faulty edges and conditional faulty edges under the PMC model.It can be divided into three chapters:In chapter 1,we mainly introduce the research background and research status of this paper and the basic concepts of graph theory.MM*model,PMC model,hypercubes,folded hypercubes and local diagnosability are also introduced.In chapter 2,we first study the diagnosability of Qn(n≥5)with faulty edges under the MM*model.We prove that Qn-F keeps strong local diagnosability property even if it has n-2 faulty edges,and its diagnosability is equal to its minimum degree.Then,we study the diagnosability of FQn(n≥6)with faulty edges under the MM*model.We prove that FQn-F keeps strong local diagnosability property even if it has n-1 faulty edges,and its diagnosability is equal to its minimum degree.In chapter 3,we first study the diagnosability of FQn(n≥4)with faulty edges under the PMC model.We prove that FQn-F keeps strong local diagnosability property even if it has n-1 faulty edges,and its diagnosability is equal to its minimum degree.Then,we study the diagnosability of FQn(n≥5 and n is odd)with conditional faulty edges under the PMC model.We prove that FQn-F keeps strong local diagnosability property even if it has 3n-4 faulty edges,provided that each vertex of FQn-F is incident with at least two fault-free edges.Its diagnosability is equal to its minimum degree.we also prove that FQn-F keeps strong local diagnosability property no matter how many edges are faulty,provided that each vertex of FQn-F is incident with at least three fault-free edges.Its diagnosability is equal to its minimum degree.