The average size of maximal matchings in graphs

, , , and

BibTeX reference

We investigate the ratio \(\mathcal{I}(G)\) of the average size of a maximal matching to the size of a maximum matching in a graph G. If many maximal matchings have a size close to \(\nu(G)\), this graph invariant has a value close to 1. Conversely, if many maximal matchings have a small size, \(\mathcal{I}(G)\) approaches \(\frac{1}{2}\).

We propose a general technique to determine the asymptotic behavior of \(\mathcal{I}(G)\) for various classes of graphs. To illustrate the use of this technique, we first show how it makes it possible to find known asymptotic values of \(\mathcal{I}(G)\) which were typically obtained using generating functions, and we then determine the asymptotic value of \(\mathcal{I}(G)\) for other families of graphs, highlighting the spectrum of possible values of this graph invariant between \(\frac{1}{2}\) and 1.

, 26 pages

Research Axis


G2213.pdf (900 KB)