The Pessimistic Diagnosability Of Three Networks Under PMC Model

In a computer system, some processors may fault, so the processor diagnosis plays an important role in the calculation of system reliability. The process for identifying the fault processor is called system diagnosis. Scholars have proposed various diagnostic models. Among the proposed models, the PMC model is widely used model introduced by Preparata, Metze and Chen. The pessimistic diagnosis strategy is a classic strategy based on the PMC model. The pessimistic diagnosability of a system G, denoted by tp(G), is the maximal number of faulty processors so that the system is t/t-diagnosed. This paper mainly studies pessimistic diagnosability of augmented cube AQn, varietal hypercube VQn and dual cube DCn under PMC model.In chapter 1, we introduce some basic definitions of graph theory and the relative background of our research and main works of this paper.In chapter 2, we consider the pessimistic diagnosability of augmented cubes AQn under PMC model. Firstly, we introduce the definition and properties of AQn; Secondly, we prove that for every U (?) V(AQn) with 2≤|U|≤ 8n-22, we have|NAQn(U)|≥ 4n-8 for n≥ 5. Finally, we obtain that the pessimistic diagnosability of AQn is 4n - 8 under PMC model.In chapter 3, we investigate the pessimistic diagnosability of varietal hypercubes VQn under PMC model. Firstly, we introduce the definition and properties of VQn; Secondly, we prove that for every U (?) V(VQn) with 2 ≤ |U| ≤ 4n-8, we have |NvQn(U)|≥2n-2 for n≥ 4; Finally, we determine that the pessimistic diagnosability of VQn is 2n-2 under PMC model.In chapter 4, we consider the pessimistic diagnosability of dual cubes DCn under PMC model. Firstly, we give the definition and properties of DCn; Secondly, we prove that for every U (?) V(DCn) with 2≤|U|≤ 4n-4, we have|NDCn(U)|≥ 2n for n≥ 3. Finally, we obtain that the pessimistic diagnosability of DCn is 2n under PMC model.In chapter 5, summarize the contents of this article and further work.