Retour

# The average size of maximal matchings in graphs

## Alain Hertz, Sébastien Bonte, Gauvain Devillez et Hadrien Mélot

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.

, 26 pages

### Document

G2213.pdf (930 Ko)