A recursive formula for the two‐edge connected and biconnected reliability of a complete graph. Issue 4 (25th April 2017)

• Record Type: Journal Article
• Authors: Lange, Thomas; Reinwardt, Manja; Tittmann, Peter
• Is Part Of: Networks. Volume 69:Issue 4(2017)
• Page Start: 408
• Page End: 414
• Publication Date: 2017-04-25
• Subjects: network reliability -- biconnected graph -- two‐edge connected graph -- integer partition -- random graph -- connectivity; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21744
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : 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. 69(4), 408–414 2017