A recursive formula for the two‐edge connected and biconnected reliability of a complete graph

The reliability polynomial R ( G , p ) of a finite undirected graph G = ( V , E ) gives the probability that the operational edges of G induce a connected graph assuming that all edges of G fail independently with identical probability q = 1 − p . In this article we investigate the probability that the operational edges of a graph with randomly failing edges induce a biconnected or two-edge connected subgraph, which corresponds to demands for redundancy or higher throughput in communication networks. The computation of the biconnected or two-edge connected reliability for general graphs is computationally intractable (#P-hard). We provide recurrence relations for biconnected and two-edge connected reliability of complete graphs. As a consequence, we can determine the number of biconnected and two-edge connected graphs with given order and size. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 000(00), 000–000 2017