Connectivity And Diagnosability Of M(?)bius Cubes

In the recent years, with the expansion of multiprocessor, the stability of each processor plays an important role in the normal operation of the parallel multiprocessor system. In order to ensure the stability of the system, a processor should be recognized by a fault-free processor whenever the fault occurs. The process of identifying the fault processors is called the diagnosis of the system. The diagnosability of the system is the maximum number of fault processors that can be replaced in the system. It plays an important role in measuring the reliability and fault tolerance of interconnection networks. In this paper,the concept of g good neighbor diagnosability is proposed. It restrains every fault-free node containing at least g fault-free neighbors.In 2015, Zhang et al. proposed a new measure for fault diagnosis of the system, namely, the g-extra diagnosability, which restrains that every fault-free component has at least g fault-free nodes. Two new diagnostic methods g-good neighbor diagnosability and g-restricted diagnosability are proposed in recent years. They are more accurate than the traditional diagnostic methods. Hypercube is a well-known basic topology in the interconnection network. As the deformation of the hypercube,n dimensional Mobius cube has better properties than the hypercube. We usually use PMC model and MM model to research the problem of fault diagnosis of the system.The MM* model is a special case of the MM model. This paper mainly studies 1 good neighbor connectivity and diagnosability and tightly super 2-extra connectivity and 2-extra diagnosability of the n dimensional Mobius cube MQn under the PMC model and MM*model . The following is the mainly content of this article:In the first chapter, this paper briefly introduce the research background and research status, some basic concepts in graph theory, the definition of n dimensional Mobius cube,as well as two famous fault diagnosis model, PMC model and MM model.In the second chapter, we introduce the concept of g-good neighbor diagnosability and prove that the 1 good neighbor connectivity of n dimension Mobius cube MQn isκ(1)= 2n-2 (n≥4), and prove that the 1 good neighbor diagnosability of the Mobius cube under the PMC model (n ≥ 4) and under the MM* model (n ≥ 5) is 2n - 1.In the third chapter, we introduce the concept of g-restricted diagnosability of multi-processor system, and proves that MQn (n ≥ 5) is tightly 3n - 5 super 2-extra connected and the 2-extra diagnosability of MQn under the PMC model (n ≥ 5) and under the MM* model (n ≥ 6) is 3n-3.