On the connectivity of graphs generated by a sum of random mappings

We consider four models of random directed multigraphs with n labeled vertices of out-degree d. First we establish formal relationships between our models with respect to exact and asymptotic (as n → ∞) probabilities of possessing a graph monotone property. We also study the asymptotic behavior of the strength of connectivity of the underlying simple graphs when d = o(n). © 1993 John Wiley & Sons, Inc.