TOPICS
Search

Reliability Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

C(p)=(1-p)^(n-c)p^(m-n+c)T(1,p^(-1)),
(1)

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

C(p)=sum_(j=1)^ma_j(1-p)^jp^(m-j),
(2)

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

C(p)=(1-p)^9(704p^6+696p^5+390p^4+155p^3+45p^2+9p+1)
(3)

(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).

graphC(p)
banana tree(x-1)^(nk)
cycle graph C_n(1-p)^(n-1)[1+(n-1)p]
gear graph((p-1)^(2n)[(-t+3p+1)^n+(t+3p+1)^n-2^(n+1)p^n])/(2^n)
ladder graph((p-1)^(2n-1))/(2^nsqrt(p(9p+2)+1))[(3p-sqrt(p(9p+2)+1)+1)^n-(3p+sqrt(p(9p+2)+1)+1)^n]
pan graph(1-p)^n[1+(n-1)p]
path graph P_n(1-p)^(n-1)
star graph S_n(1-p)^(n-1)
sunlet graph C_n circledot K_1(1-p)^(2n-1)[(1+(n-1)p]

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

graphorderrecurrence
cycle graph C_n2p_n(x)=-2(x-1)p_(n-1)(x)-(x-1)^2p_(n-2)(x)
gear graph3p_n(x)=(4x+1)(x-1)^2p_(n-1)(x)-x(3x+2)(x-1)^4p_(n-2)(x)+x^2(x-1)^6p_(n-3)(x)
ladder graph L_n2p_n(x)=(3x+1)p_(n-1)(x)-xp_(n-2)(x)
pan graph2p_n(x)=-2(x-1)p_(n-1)-(x-1)^2p_(n-2)(x)
path graph P_n1p_n(x)=(1-x)p_(n-1)(x)
star graph S_n1p_n(x)=(1-x)p_(n-1)(x)
sunlet graph C_n circledot K_12p_n(x)=2(x-1)^2p_(n-1)(x)-(x-1)^4p_(n-2)(x)
wheel graph W_n3p_n(x)=-(3x+1)(x-1)p_(n-1)(x)-2x(x+1)(x-1)^2p_(n-2)(x)-x^2(x-1)^3p_(n-3)(x)

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

nreliability polynomialgraphs
4-(-1+x)^3claw graph, path graph P_4
5(-1+x)^4fork graph, path graph P_5, star graph S_5
5(-1+x)^4(1+2x)bull graph, cricket graph, (3,2)-tadpole graph
5(-1+x)^4(1+3x+4x^2)dart graph, kite graph

See also

Rank Polynomial, Tutte Polynomial

Explore with Wolfram|Alpha

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

Subject classifications