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