๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Random Matchings in Regular Graphs

โœ Scribed by Jeff Kahn; Jeong Han Kim

Publisher
Springer-Verlag
Year
1998
Tongue
English
Weight
339 KB
Volume
18
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Random Matchings Which Induce Hamilton C
Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs
โœ Jeong Han Kim; Nicholas C. Wormald ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 215 KB

Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set

Small maximal matchings in random graphs
Small maximal matchings in random graphs
โœ Michele Zito ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 204 KB

We look at the minimal size of a maximal matching in general, bipartite and d-regular random graphs. We prove that with high probability the ratio between the sizes of any two maximal matchings approaches one in dense random graphs and random bipartite graphs. Weaker bounds hold for sparse random gr