Reachability problems of random digraphs

Consider a random digraph G = (V, A), where \V\ = n and an are (u, v) is pr esent in A with probability p(n) independent of the existence of the other arcs. We discuss the expected number of vertices reachable from a vertex, t he expected size of the transitive closure of G and their related topics ba sed on the properties of reachability, where the reachability from a vertex s to t is defined as the probability that s is reachable to t. Let gamma(n ,p(n)) denote the reachability s to (not equal s) in the above random digra ph G. (In case of s = t, it requires another definition.) We first present a method of computing the exact value of gamma(n,p(n)) for given n and p(n) . Since the computation of gamma(n,p(n)) by method requires O(n(3)) time, w e then derive simple upper and lower bounds gamma(n,p(n))(U) and gamma(n,p( n))(L) on gamma(n,p(n)), respectively, and in addition, we give an upper bo und <(gamma)over bar>(n,p(n)) on gamma(n,p(n))(U), which is easier to analy ze but is still rather accurate. Then, we discuss the asymptotic behavior o f <(gamma)over bar>(n,p(n)) and show that, if p(n) = alpha/(n-1), lim(n-->i nfinity) <(gamma)over bar>(n,p(n)) converges to one of the solutions of the equation 1-x-e(-alpha x) = O. Furthermore, as for (R) over bar(n) and (T) over bar(n), which are upper bounds on the expected number of reachable ver tices and the expected size of the transitive closure of G, resp., it turns out that lim(n-->infinity) (R) over bar(n) = alpha/(1-alpha) if p(n) = alp ha/(n-1) for 0 < alpha < 1; otherwise either 0 or infinity, and lim(n-->inf inity) (T) over bar(n) = alpha if p(n) = alpha/(n-1)(2) for alpha greater t han or equal to 0; otherwise either 0 or infinity.