Percolation theory on directed graphs

The pair connectivity P_uv of a directed graph G between vertices u and v is the probability that there is a path from u to v when each edge and vertex has a given probability of being deleted, deletions being made independently. We consider the coefficient $\mathrm{d⃗}$ in the expansion P_uv(G) = Σ_A′⊇A $\mathrm{d⃗}$ _uv(G′) Π_aεA′p_a Π_wεV′p_w, where A and V are respectively the arc and vertex sets of G, and p_a(p_w) is the probability that the arc a (vertex w) is not deleted. G′ is the arc set A′ together with its set of incident vertices V′. It is shown that $\mathrm{d⃗}$ _uv(G′) is nonzero if and only if G′ is coverable by some set of (directed) paths from u to v and has no circuit. When these conditions are satisfied, $\mathrm{d⃗}$ _uv(G′) = (−1)^t_uv+1 where the number of independent paths from u to v is t_uv. Moreover, t_uv is shown to have the value of ν (G)+1, ν (G) being the cyclomatic number of the graph G.