Matchings in Random Regular Bipartite Digraphs.
Abstract
Let G be a random directed bipartite graph with n nodes in each class and outward degree d at each node. The probability G contains a matching is shown to approach one for large n if d > or = 2, but to approach zero if d = 1. This result complements and contrasts with a result of Erdos and Renyi which implies the probability of a matching does to zero if the number of arcs (chosen at random without regard to regularity) grows more slowly than n log n.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1974
- Accession Number
- ADA012380
Entities
People
- David W. Walkup
Organizations
- University of Washington