Study On Several Issues In The Design Of Network Reliability

Consider a network represented by a graph G with a probability of vertex failure p and a probability of edge failure q. The reliability of G, denoted by R(G), is the connected probability of all vertices in G. The main aim of network reliability design is to find networks with maximum network reliability with given number of vertices and edges. Results on network reliability design is very important and helpful for designing reliable network.In this thesis, we mainly investigate several problems appearing in the study of network reliability design.In Chapter 1, after an introduction of the terminology and notations employed in this paper, we give a survey on network reliability design and an overview of the main results of this thesis.In Chapter 2, we mainly investigate τ-optimal graphs. We give several new structural properties of r-optimal graphs and obtain some new r-optimal graphs.In Chapter 3, for simple graphs with n perfectly reliable vertices and e edges which fail independently and with the same probability q, we mainly investigate the uniformly most reliable graphs in the case. n = 7 and 6 ≤ e ≤ 21, and study the structure of the uniformly most reliable graphs of with n vertices and n + 4 edges.In Chapter 4, for simple graphs with e perfectly reliable edges and n vertices which fail independently and with the same probability p, we give some new families of S₃-minimum graphs.We conclude the thesis by discussing some problems for further research in Chapter 5.