Two Kinds Of Index For Network Reliability

In this paper, we study two kinds of index to measure the reliability of network. For a graph G, suppose that edges never fail and vertices operate independently for each other with a constant probability p∈[0,1], G is called network of vertices fail. In this case, a significant index of network reliability is called uniformly optimal. For all vertex-failure probabilities p, if the graph G is the most reliable graph in their classes, the graph G is the uniformly optimal graph. we prove that the complete k-partite graphs K(b,(b+2)k-1) are uniformly optimal in their classes, while for i≥3, the complete k-partite graphs K(b,(b+2)k-2, b+i) are not uniformly optimal in their classes.For a graph G, suppose that vertices never fail and edges fail independently of each other with a constant probability, G is called network of edges fail. If two net-works have same edge-connectivity, a significant index, restricted edge-connectivity, is presented in order to more accurately compare with other networks. The restricted edge-connectivity of a connected graph G, λ’(G), is defined to be the minimum num-ber of edges whose deletion results in a disconnected graph such that each connected component has at least two vertices. For any graph G even without restricted edge cut set, we prove that λ’(G×Kn)=min{(n-1)ξ(G)+2(n-2),n(n-1)λ’(G)} for n≥3, whereξ(G) is minimum edge-degree of G. As a result, a sufficient condition for optimizing the restricted edge connectivity of these graphs are presented.