错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The average size of maximal matchings in graphs

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

摘要

We investigate the ratio \(\mathcal {I}(G)\) 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)\) ν ( G ) , this graph invariant has a value close to 1. Conversely, if many maximal matchings have a small size, \(\mathcal {I}(G)\) I ( G ) approaches \(\frac{1}{2}\) 1 2 . We propose a general technique to determine the asymptotic behavior of \(\mathcal {I}(G)\) 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)\) I ( G ) which were typically obtained using generating functions, and we then determine the asymptotic value of \(\mathcal {I}(G)\) I ( G ) for other families of graphs, highlighting the spectrum of possible values of this graph invariant between \(\frac{1}{2}\) 1 2 and 1.