A Recursive Formula for the Reliability of a r -Uniform Complete Hypergraph and Its Applications

Abstract EN

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.