Random Bipartite Graphs: Connectedness, Isolated Nodes, Diameters.
Abstract
Let B(m,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 m(1), m(2),... and E(1), E(2),... are such that m(n) is less than or = n and E(n) is less than or = m(n)n for all n, and lim inf as n approaches infinity E(n)/(n log n) is greater than 1, then the probability that a random member of B approximate (m(n),n,E(n)) is connected converges to 1 as n approaches infinity. Results on isolated nodes and on diameters are also obtained. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1979
- Accession Number
- ADA070100
Entities
People
- David Larman
- Victor Klee
Organizations
- University of Washington