Let D(n,r) be a random r-out regular directed multigraph on the set of vertices 1,...,n . In this work, we establish that for every r � 2, there existsr > 0 such that diam(D(n,r)) = (1 + �r + o(1))log r n. Our techniques also allow us to bound some extremal quantities related to the stationary distribution of a simple random walk on D(n,r). In particular, we determine the asymptotic behaviour ofmax andmin, the maximum and the minimum values of the stationary distribution. We show that with
To conclude this section, we discuss the stationary distribution of a simple random walk in these other models. While in undirected graphs the stationary distribution (if it exists) is completely determined by the degrees of the vertices, this is not the case in directed graphs. Cooper and Frieze @cite_10 give a very precise description of the stationary distribution of @math when @math , for any constant @math , and use their result to compute the cover time of @math . It is worth noticing that for such values of @math , both the in-degrees and out-degrees are of logarithmic order and concentrated around their expected values, which turns to be very useful for the analysis. It seems harder to find an interesting question about the stationary distribution of @math when @math since like in random @math -in regular digraphs, typically there are vertices with no out-edges.
@cite_10
2158978530
We study properties of a simple random walk on the random digraph D"n","p when np=dlogn, d>1. We prove that whp the value @p"v of the stationary distribution at vertex v is asymptotic to deg^-(v) m where deg^-(v) is the in-degree of v and m=n(n-1)p is the expected number of edges of D"n","p. If d=d(n)-> with n, the stationary distribution is asymptotically uniform whp. Using this result we prove that, for d>1, whp the cover time of D"n","p is asymptotic to dlog(d (d-1))nlogn. If d=d(n)-> with n, then the cover time is asymptotic to nlogn.