The random bipartite nearest neighbor graphs. (English) Zbl 0936.60005
Summary: The bipartite \(k\)th nearest neighbor graphs \(B_k\) are studied. It is shown that \(B_1\) has a limiting expected matching number of approximately \(80 \%\) of its vertices, that with high probability (whp) \(B_2\) has at least \(2 \log n/13 \log\log n\) vertices not matched, and that whp \(B_3\) does have a perfect matching. We also find a formula for the limiting probability that \(B_2\) is connected and show that whp \(B_3\) is connected.
MSC:
| 60C05 | Combinatorial probability |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Cooper, Combin Probab Comput 4 pp 343– (1996) · Zbl 0846.05078 · doi:10.1017/S0963548300001711 |
| [2] | and Constructive bounds and exact expectations for the random assignment problem, IBM Research Report, 1998. |
| [3] | Dyer, Math Programming 35 pp 3– (1986) |
| [4] | Lecture at the NIHE Summer School on Combinatorial Optimization, Dublin, 1983. |
| [5] | Karp, Math Oper Res 19 pp 513– (1994) |
| [6] | The assignment problem with uniform (0, 1) cost matrix, B.A. thesis, Department of Mathematics, Princeton University, Princeton, NJ, , 1979. |
| [7] | and The expected node-independence number of various types of trees, Recent Advances in Graph Theory, Academia, Prague, 1975, pp. 351-363. |
| [8] | Nanda, Random Struct Alg 15 pp 000– (1999) |
| [9] | Asymptotic properties of random assignment problems, Ph.D. thesis, Kungl Tekniska Högskolan, Stockholm, Sweden, 1992. |
| [10] | Pittel, Ann Appl Probab 2 pp 358– (1992) |
| [11] | Pittel, J Appl Probab 27 pp 522– (1987) |
| [12] | Pittel, Ann Appl Probab 9 (1999) |
| [13] | Walkup, SIAM J Comput 8 pp 440– (1979) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
