The 1-good-neighbour Diagnosability Of Augmented K-ary N-cubes And 2-extra Connectivity Of Exchanged Crossed Cubes

Many multiprocessor systems have interconnection networks(networks for short)as underlying topologies and a network is usually represented by a graph where vertices repre-sent processors and edges represent communication links between peocessors.we use graphs and networks interchangeably.Connectivity plays an important role in measuring the fault tolerance of the interconnection networks.Since a large-scale computer system is made up of thousands of the computer processors,more processors may fail in such a complex op-eration environment.In order to better study the fault tolerance of the system,in 1996,J.Fabrega and M.A.Fiol introduced the k-extra connectivity of the interconnection net-works.Diagnosability is a significant parameter in measuring the fault diagnosis of the multiprocessor systems.However,some processors may be faulty in the system.There-fore,in order to ensure the reliability of the computer system,the faulted processor system should be diagnosed and replaced by some fault-free processors.The process of identifying the faulty processors is called the diagnosis of the system.Diagnosability is defined as the maximum number of faulty processors which the system can guarantee to identify.The traditional diagnosability allows that the neighbors of any processor are failed at the same time.However,the possibility of this failure is very small in a large multiprocessor systems.Therefore,in 2015,Lai et al.proposed the conditional diagnosability of the system,which restricts that any processor is adjacent to at least a non-faulted processor in a system.In 2012,Peng et al.put forword the g-good neighbour diagnosability of the system,which requires that every fault-free vertex has at least g fault-free neighbours.And Peng et al.studied the g-good-neighbor diagnosability of Qn under the PMC model.To measure the diagnosability of multiprocessor systems,many diagnosis model have been proposed.In particular,the PMC model and the MM*model,these two models were widely used.There are many studies under the PMC model and the MM*model.The following is the main content of this paper:In the first chapter:we briefly introduce research background and research status,give some concepts of graph theory,the definitions of augmented k-ary n-cubes AQn,k and exchanged crossed cubes ECQ(s,t),and also two famous fault diagnosis models,i.e.,PMC model and MM*model.In the second chapter:we prove that the 1-good-neighbor diagnosability of augmented k-ary n-cubes under the PMC model the MM*model is 8n-9(n ? 4,k? 4).In the third chapter:we prove that the 2-extra connectivity of exchanged crossed cubes ECQ(s,t)is 3s—2(2 ? s ? t).In the fourth chapter:summary of the work.