ABSTRACT
The reliability polynomial R (G; p) of a graph G = (V;E) is the the all-terminal reliability of G under the assumption that all edges fail independently with identical probability p. Hence all properties of the all-terminal reliability introduced in Section 5.1 apply directly to the reliability polynomial. From Equation (5.1), we obtain
R (G; p) = X FE
(G [F ]) pjF j (1 p)jEnF j : (6.1)
Let G = (V;E) be a graph with n vertices and m edges. Since any path set of G must contain at least n 1 edges and at most m edges, we obtain a polynomial of the following form
R (G; p) = mX
i=n1 aip
i. (6.2)
If the given graph G is not connected, then there exists no path set and the reliability polynomial ofG is identically zero. IfG is connected thenG contains at least one spanning tree, i.e. a path set of cardinality n 1. The complete edge set E (G) forms a path set for each connected graph G. Consequently, R (G; p) is a polynomial of degree m and of low degree n 1 (smallest power of p). The coe¢ cient an1 is the number of spanning trees of G, which can be computed e¢ ciently (in polynomial time) by the matrix tree theorem of Kirchho¤, see e.g. [64].
