On the Reliability of Unicyclic Networks with Vertex Failure

For a graph G with perfectly reliable edges and unreliable vertices, we consider the reliability of G for which vertices fail independently of each other with a constant probability p. The reliability of graph G, denoted by P_n(G,p), is defined to be the probability that the induced subgraphs of surviving vertices connected. Denote by Ω(n,m) the family of connected graphs with n vertices and m edges. In this paper, we determine the optimal value of each coefficient of R_n(G,p) and the corresponding graphs for G ∈ Ω(n, n +1) and n ≥ 6. As a byproduct, we give the locally optimal graphs in Ω(n,n + 1), for n ≥ 8.