Expected value expansions in rooted graphs Original Research Article

When G is a rooted graph where each edge may independently succeed with probability p, we consider the expected number of vertices in the operational component of G containing the root. This expected value EV(G;p) is a polynomial in p. We present several distinct equivalent formulations of EV(G;p), unifying prior treatments of this topic. We use results on network resilience (introduced by Colbourn) to obtain complexity results for computing EV(G;p). We use some of these formulations to derive closed form expressions for EV(G;p) for some specific classes of graphs. We conclude by considering optimality questions for rooted graphs, root placement and some counterexamples.