The optimal unicyclic graphs for pair-connected reliability

AbstractWe 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 → ∞