Fault-tolerance And Conditional Fault-tolerance Of Some Networks

Fault-tolerance has played an important role in the reliability of an interconnection network. Fault-tolerance is the foundation of the network security and diagnosis. In this dissertation, we show the fundamental theory and methods to study the conditional fault-tolerance of topological structure of interconnection networks. We apply them to some networks. The main contribution of this dissertation can be summarized as follows:First we introduce the basic theory of the conditional fault-tolerance for networks under the different models, there are two kinds of main models:PMC model and MM model. We will introduce the difference between the two models, and the properties and some known conclusions under the two kinds of the models.The hypercube-like graphs contain several well-known interconnection networks such as hypercube, twisted cube and locally twisted cube. Then we will summarize some properties of the vertex fault-tolerance of the hypercube-like graphs, and give some conclusions of the conditional fault-tolerance of the hypercube-like graphs under MM model.Then we will introduce another network:the balanced hypercube. Assume that the balanced hypercube has fault edges, we prove that there exists a fault-free Hamiltonian path between any adjacent vertices. And we also prove that every fault-free edge is in a fault-free Hamiltonian cycle. Then we will give some conclusions of the conditional fault-tolerance of the balanced hypercube under MM model.Finally we summarize some properties of the vertex fault-tolerance of the star graph, and give a sufficient condition of any two conditional fault vertex sets are distinguishab-le under the PMC model.