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

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.