Reliability Polynomial

Let G be a graph, and suppose each edge of G is independently deleted with fixed probability 0<=p<=1. Then the probability that no connected component of G is disconnected as a result, denoted C(p) is known as the reliability polynomial of G.

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


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


where a_j is the number of subgraphs of the original graph G having exactly j edges and for which every pair of nodes in G is joined by a path of edges lying in subgraph S (i.e., S is connected and |S|=n), which is the definition due to Page and Perry (1994) after making the change p->1-p.

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


(Godsil and Royle 2001, p. 355).

The following table summarizes simple classes of graphs having closed-form reliability polynomials. Here, t=sqrt(1+2x+9x^2).

The following table summarizes the recurrence relations for reliability polynomials for some simple classes of graphs.

Nonisomorphic graphs do not necessarily have distinct reliability polynomials. The following table summarizes some co-reliability graphs.

See also

Rank Polynomial, Tutte Polynomial

Explore with Wolfram|Alpha


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., 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.

Subject classifications