Diagnosability And Fault Tolerance Of Interconnection Network

The topological structure of interconnection network can be represented by an undirected graph ?EVG),(, where V, a set of nodes, is represented by a processor in a system and E, a set of edges, is represented by communication link between a pair of processors in a system. With the development of technology, a multiprocessor system may contain hundreds or even thousands of processors, there may be faulty nodes when the system is put into use. Thus, it is important to research the diagnosability and fault tolerance of a multiprocessor system.In this dissertation, we main discuss diagnosability of Cayley graphs generated by transposition trees and extra connectivity of crossed cube.To diagnose the faulty nodes in a multiprocessor, there are two classical diagnosis models have been proposed: PMC model and comparison diagnosis model(MM model). In [Zheng J, Latifi S, Regentova E, et al. Diagnosability of star graphs under the comparison diagnosis model[J]. Information Processing Letters, 2005, 93(1):29-36.], the n-dimensional star graphnS has been proved to be n)1(?? diagnosable under the comparison diagnosis model when n?4. Star graphs belongs to a class of Cayley graphs generated by transposition trees. In the second of this paper, Cayley graphs generated by transposition trees have been proved to be n)1(?? diagnosable under the comparison diagnosis model when n?5.Connectivity and super connectivity are important measures of multiprocessor system.As a generalization of super connectivity, extra connectivity received much research attentions recently. Let h be a non-negative integer. A vertex-set ?GVS)( is called an h? extra vertex-cut if SG ? is disconnected and every component of SG ? has more than h vertices. The h? extra connectivity of G is defined as the cardinality of a minimum h? extra vertex-cut, if exist. In the third chapter of this paper, by researching the boundary problem of crossed cube, we obtained that g? extra connectivity of crossed cube.