The average size of maximal matchings in graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914707684720640 |
|---|---|
| author | Hertz, Alain Bonte, Sébastien Devillez, Gauvain Mélot, Hadrien |
| author_facet | Hertz, Alain Bonte, Sébastien Devillez, Gauvain Mélot, Hadrien |
| contents | We investigate the ratio $\avM(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 $\maxM(G)$, this graph invariant has a value close to 1. Conversely, if many maximal matchings have a small size, $\avM(G)$ approaches $\frac{1}{2}$.
We propose a general technique to determine the asymptotic behavior of $\avM(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 $\avM(G)$ which were typically obtained using generating functions, and we then determine the asymptotic value of $\avM(G)$ for other families of graphs, highlighting the spectrum of possible values of this graph invariant between $\frac{1}{2}$ and $1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_10236 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The average size of maximal matchings in graphs Hertz, Alain Bonte, Sébastien Devillez, Gauvain Mélot, Hadrien Combinatorics Discrete Mathematics We investigate the ratio $\avM(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 $\maxM(G)$, this graph invariant has a value close to 1. Conversely, if many maximal matchings have a small size, $\avM(G)$ approaches $\frac{1}{2}$. We propose a general technique to determine the asymptotic behavior of $\avM(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 $\avM(G)$ which were typically obtained using generating functions, and we then determine the asymptotic value of $\avM(G)$ for other families of graphs, highlighting the spectrum of possible values of this graph invariant between $\frac{1}{2}$ and $1$. |
| title | The average size of maximal matchings in graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2204.10236 |