LEAST RELIABLE NETWORKS AND THE RELIABILITY DOMINATION

A well-known model in communication network reliability consists of an undirected graph G whose edges operate independently with the same probability p. Then the reliability, R(G, p) of G, is the probability that G is connected. It is known that R(G,p) is a polynomial in p and its coefficients are invariants of G. In particular, the coefficient of the least order term is the number of spanning trees t(G), while the coefficients of the highest order term is the reliability domination d(G) of G. Presented is a complete characterization of graphs that achieve the minimum absolute value \ d(G)\ over the class of n-node, e-edge connected graphs. Furthermore, the class of graphs that yield minimum t(G) is shown to minimize \ d(G)\. These results have applications in the synthesis of least reliable networks.