Small maximal matchings in random graphs

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Review text

The author considers general, bipartite, and \(d\)-regular random graphs. The main results are bounds for the minimum size of a maximal matching \(\beta(G)\). For example, it is shown that \(n/2 - \log n/\log(1/1-p) < \beta(G) < n/2 - \log n/2\log(1/1-p)\) for almost every graph with \(n\) vertices and \(p\) being constant. Similar bounds are also valid for random bipartite graphs. What concerns \(d\)-regular random graphs, for each \(d\geq 3\) there exists a constant \(\gamma(d)\) such that \(\beta(G)\geq \gamma(d)n\) for almost every graph with \(n\) vertices and \(p\) being constant. In the later case an algorithm is developed that with a high probability finds a maximal matching of size asymptotically less than \(|V(G)|/2\). A detailed analysis for 3-regular random graphs provides \(0.3158n < \beta(G) < 0.47563n\). For the entire collection see [Zbl 0935.00049].

Recommendations

Cited in

(15)

This page was built for publication: Small maximal matchings in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508359)