On the validity of a reduction of reliable network design to a graph extremal problem

An undirected connected graph having failure probabilities associated with each edge is a classic model for network reliability studies. The network reliability is defined as the probability that the graph remains connected despite edge failures. It is known that the problem of calculating the network reliability isNP-hard, even when the edge failures are equal and independent. Herein, we consider synthesis problems for the equal edge failure rate case. Specifically, we treat the case where the number of pointsp, the number of edgesq, and the edge failure rate given; the synthesis problem is to find ap-point,q-edge graph that maximizes the network reliability for the givenρ. A simple intuitive argument indicates that this synthesis problem can be reduced to a solvable graph extremal question when small. Here we formalize this observation by giving explicit formulas for a range(0 < ρ ≤ ρ_0)of which allows the reliability synthesis problem to be reduced to this graph extremal question. We also discuss the possibility of extending this type of result to all possible(0 < ρ{≤}1)thereby obtaining a uniformly optimum graph. The problem of ascertaining the existence of such graphs remains open; however, we suggest several possible approaches. We also relate some reliability questions to unsolved graph extremal problems involving the maximum and minimum number of spanning trees among allp-point,q-edge graphs. Several conjectures regarding these latter problems are presented.