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.