Random Bipartite Graphs: Connectedness, Isolated Nodes, Diameters.
WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Pagination or Media Count:
Let Bm,n,E denote the family of all labeled bipartite graphs that have m nodes in the first part and n nodes in the second, with exactly E edges. If the postive integers m1, m2,... and E1, E2,... are such that mn is less than or n and En is less than or mnn for all n, and lim inf as n approaches infinity Enn log n is greater than 1, then the probability that a random member of B approximate mn,n,En is connected converges to 1 as n approaches infinity. Results on isolated nodes and on diameters are also obtained. Author
- Statistics and Probability