G-2022-13
The average size of maximal matchings in graphs
, , et
référence BibTeXWe 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. 
Paru en avril 2022 , 26 pages