Connectivity And Diagnosability Of The Augmented 3-ary N-cubes

Diagnosability is defined as the maximum number of faulty processors which the sys-tem can guarantee to identify.It is an important parameter in the fault diagnosis of multiprocessor systems,which plays an important role in measuring the reliability of the interconnection networks.In 1997,Preparata et al.first introduced system-level diagnosis,which can test the processors automatically by the system itself.The study of system-level theory depends on the establishment of the model.Many system-level diagnosis models have been proposed to identify the faulty processors.Among the proposed models,two major approaches are the PMC diagnosis model and MM*model.They were introduced by Preparata et al.and Maeng and Malek respectively.The tests under the PMC model are performed primarily through mutual testing between two adjacent processors.The MM*model is tested by sending the same task to its two neighbors,and then comparing the results of their feedback.The traditional diagnosability suggests that all the neighbor vertices of any vertex were faulty simultaneously,but this possibility is difficult to show in practice.In 2005,Lai et al.improved the traditional diagnosability and put forward the conditional diagnosability,which requires every fault-free processor in the system at least connected to a good processor.In 2012,Peng et al.further proposed the g-good-neighbor diagnosability on the basis of conditional diagnosability,which restricts that every fault-free node contains at least g fault-free neighbors.Connectivity plays an important role in the study of fault diagnosis,which is an important indicator of measuring system fault tolerance.A system of connectivity is less than its minimum degree.With the increase in the size of the system,the probability of processor faulty is bound to increase.In order to better research fault-tolerance of the system,many scholars have done extensive research on the problem of system connectivity.In this paper,the g-good-neighbor connectivity is a generalization of the traditional connectivity.The g-good-neighbor connectivity of a system G,denoted by ?(g)(G),is the minimum cardinality over all g-good-neighbor cut of G.In this paper,there are four major parts.In the first part,we briefly introduce research background and research status,some concepts of graph theory,the definitions of the augmented 3-ary n-cubes AQn,3,and also two famous fault diagnosis models,i.e.PMC model and MM*model;In the second part,we first prove that the 1-good-neighbor diagnosability of the augmented 3-ary n-cubes AQn,3 is 8n-10 for n ? 4;In the third part,we first prove that the 2-good-neighbor connectivity of the augmented 3-ary n-cubes AQn,3 is 12-24 for n ? 4,and we also prove that the 2-good-neighbor diagnosability of 3-ary n-cubes AQn,3 is 12n-22 under the PMC model and MM*model(n ? 4);In the fourth chapter,we summarize the relevant conclusions of this paper.