chapter  6
30 Pages

Connectedness in Undirected Graphs

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