 TOPICS  # Reliability Polynomial

Let be a graph, and suppose each edge of is independently deleted with fixed probability . Then the probability that no connected component of is disconnected as a result, denoted is known as the reliability polynomial of .

The reliability polynomial is directly expressible in terms of the Tutte polynomial of a given graph as (1)

where is the vertex count, the edge count, and the number of connected components (Godsil and Royle 2001, p. 358; error corrected). This is equivalent to the definition (2)

where is the number of subgraphs of the original graph having exactly edges and for which every pair of nodes in is joined by a path of edges lying in subgraph (i.e., is connected and ), which is the definition due to Page and Perry (1994) after making the change .

For example, the reliability polynomial of the Petersen graph is given by (3)

(Godsil and Royle 2001, p. 355).

The following table summarizes simple classes of graphs having closed-form reliability polynomials. Here, .

 graph banana tree cycle graph  gear graph ladder graph pan graph path graph  star graph  sunlet graph  The following table summarizes the recurrence relations for reliability polynomials for some simple classes of graphs.

 graph order recurrence cycle graph 2 gear graph 3 ladder graph 2 pan graph 2 path graph 1 star graph 1 sunlet graph 2 wheel graph 3 Nonisomorphic graphs do not necessarily have distinct reliability polynomials. The following table summarizes some co-reliability graphs. reliability polynomial graphs 4 claw graph, path graph 5 fork graph, path graph , star graph 5 bull graph, cricket graph, -tadpole graph 5 dart graph, kite graph

Rank Polynomial, Tutte Polynomial

## Explore with Wolfram|Alpha More things to try:

## References

Brown, J. I. and Colbourn, C. J. "Roots of the Reliability Polynomial." SIAM J. Disc. Math. 5, 571-585, 1992.Chari, M. and Colbourn, C. "Reliability Polynomials: A Survey." J. Combin. Inform. System Sci. 22, 177-193, 1997.Colbourn, C. J. The Combinatorics of Network Reliability. New York: Oxford University Press, 1987.Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications I: The Tutte Polynomial." 28 Jun 2008. http://arxiv.org/abs/0803.3079.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 354-358, 2001.Page, L. B. and Perry, J. E. "Reliability Polynomials and Link Importance in Networks." IEE Trans. Reliability 43, 51-58, 1994.Royle, G.; Alan, A. D.; and Sokal, D. "The Brown-Colbourn Conjecture on Zeros of Reliability Polynomials Is False." J. Combin. Th., Ser. B 91, 345-360, 2004.

## Referenced on Wolfram|Alpha

Reliability Polynomial

## Cite this as:

Weisstein, Eric W. "Reliability Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ReliabilityPolynomial.html