Premium
A recursive formula for the two‐edge connected and biconnected reliability of a complete graph
Author(s) -
Lange Thomas,
Reinwardt Manja,
Tittmann Peter
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21744
Subject(s) - biconnected graph , combinatorics , computer science , strongly connected component , enhanced data rates for gsm evolution , graph , undirected graph , reliability (semiconductor) , connected component , mathematics , discrete mathematics , line graph , voltage graph , telecommunications , power (physics) , physics , quantum mechanics
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