A recursive formula for the reliability of a \(r\)-uniform complete hypergraph and its applications (Q1720743)

Summary: The reliability polynomial \(R(S, p)\) of a finite graph or hypergraph \(S = (V, E)\) gives the probability that the operational edges or hyperedges of \(S\) induce a connected spanning subgraph or subhypergraph, respectively, assuming that all (hyper)edges of \(S\) fail independently with an identical probability \(q = 1 - p\). In this paper, we investigate the probability that the hyperedges of a hypergraph with randomly failing hyperedges induce a connected spanning subhypergraph. The computation of the reliability for (hyper)graphs is an NP-hard problem. We provide recurrence relations for the reliability of \(r\)-uniform complete hypergraphs with hyperedge failure. Consequently, we determine and calculate the number of connected spanning subhypergraphs with given size in the \(r\)-uniform complete hypergraphs.