Network Reliability With Node Failures

Consider a network represented by a grahp 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 connectedprobability 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 are very important and helpful for designing reliable network.In this thesis, we mainly investigate the design problem of uniformly optimally reliablenetwork whose edges never fail but whose vertices break down indeependently of each other.In Chapters 1 and 2, 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 3, we mainly intrestigate the problem of uniformly optimally reliable networkwith given munber of vertices and edges. We give two new classes of uniformly optimallyreliable network. More precisely, we prove that for any positive integer b(b≥2), the complete k-partite graph (?) and (?) are uniformly optimally reliable in corresponding classes, while the complete k-partite graphs (?) are not the unifomly optimallyreliable in their classes.In Chapter 4, when uniformly optimally reliable graphs not exist, we give the maximumvalue of each coefficient of the reliability polynomials of the graphs with only vertex failure and the corresponding graphs for the families of graphsΩ(n. n + 2).We conclude in Chapter 5 of the thesis by discussing some problems for further reseach.