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
We consider the complete graph K_n on n vertices with exponential mean n edge lengths. Writing C_ ij for the weight of the smallest-weight path between vertex i,j [n], Janson [17] showed that max_ i,j [n] C_ ij log n converges in probability to 3. We extend this results by showing that max_ i,j [n] C_ ij - 3 log n converges in distribution to some limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centered graph diameter of the barely supercritical Erdos-Renyi random graph in [21]. Consider the minimal weights of paths between two points in a complete graph Kn with random weights on the edges, the weights being, for instance, uniformly distributed. It is shown that, asymptotically, this is log n n for two given points, that the maximum if one point is fixed and the other varies is 2 log n n, and that the maximum over all pairs of points is 3 log n n.Some further related results are given as well, including results on asymptotic distributions and moments, and on the number of edges in the minimal weight paths.