The optimal unicyclic graphs for pair-connected reliability (Q1208486)

In a graph in which each edge operates independently with probability \(p\), the pair-connected reliability is the expected number of vertex pairs connected by paths of operating edges. Trees that maximize pair- connected reliability are stars, for every probability \(p\). For unicyclic graphs on \(k\) vertices, the authors establish that there is no such optimum; indeed, for each cycle length \(c\), \(3\leq c\leq k\), there is a probability \(p_ c\) and a \(k\)-vertex unicyclic graph \(G_ c\) having a \(c\)-cycle for which \(G_ c\) is the optimal \(k\)-vertex unicyclic graph for edge probability \(p_ c\).