The optimal unicyclic graphs for pair-connected reliability

The authors consider the standard network reliability model in which each edge of a graph fails, independently of all others, with probability q=1-p(0•p•1). The pair-connected reliability of the graph is the expected number of pairs of vertices that remain connected after the edge failures. The optimal graphs for pair-connected reliability in the class of unicyclic graphs (connected (n,n) graphs) are completely characterized. The limiting behavior of the intervals of optimality are studied as n⇒•.