Some Parameters Of Kautz Disgraphs With Respect To Fault Tolerance

The network of a supercomputing system has a decisive effect on the performance of the system.When a network is modeled by a graph,the performance of the network can be measured by the properties and parameters of the graph.In practice,failure of some com-ponents is inevitable.Therefore,in order to ensure the normal operation of the system,it is very necessary to study the fault tolerance of the system.The classical parameter to measure fault tolerance is connectivity,and the good-neighbor connectivity is a more accurate fault tolerance parameter than connectivity.A network with maximum connectivity is the one with high reliability in some sense.Maximally local connectivity and super connectivity are two properties with higher requirements than maximum connectivity.In recent years,re-search on fault tolerance with respect to maximally local connectivity and super connectivity of graphs has been paid a lot of attention.The diagnosability of a system is a parameter used to measure the self-diagnosis capability of the system.The good-neighbor diagnosabili-ty is a more accurate index than traditional diagnosability.At present,the research of these parameters is mainly focused on the graph.Kautz digraphs are a kind of important networks of super computing systems.This thesis will determine these parameters for Kautz digraphs The details are as followsChapter 1 first explains the concepts involved in this thesis,and then introduces the research trends in this areaChapter 2 first generalizes the concept of restricted connectivity of graphs to digraphs proposes strongly restricted connectivity ?2(D)?good-neighbor connectivity k(1)(D)?2 re-stricted connectivity ?2(D)and restricted connectivity ?'(D),and prove ?2(D)??(1)(D)??2(D)??'(D).Next,a characterization of superconnected digraphs are given.Finally some properties of Kautz digraphs are studied and it is proved that the good-neighbor connectivity of the Kautz digraph K(d,n)with d? 2,n?2 and(d,n)?(2,2)is?(1)(k(d,n))=2d-2.Chapter 3 first shows that Kautz digraphs are maximally local connected,and then proves that the fault tolerance with respect to maximally local connectivity of the Kautz digraph K(d,n)with d>2 and n? 2 is ?(K(d,n))= d-2.Finally we determine that the fault tolerance with respect to super connectivity of the Kautz digraph K(d,n)with d?4 and n?2 is S?(K(d,n))=d-1.Chapter 4 proves that the diagnosability of the Kautz digraph K(d,n)with d?1 and n?1 under the PMC model is t(K(d,n))=d and the good-neighbor diagnosability of the Kautz digraph K(d,n)with d?2,n? 2 and(d,n)?(2,2)under the PMC model is t1(K(d,n))=2d-1 based on the good-neighbor connectivity of Kautz digraphs.