Minimum maximal matchings in cubic graphs

Wouter Cames van Batenburg¹

¹Université Libre de Bruxelles

The electronic journal of combinatorics, Tome 29 (2022) no. 2

Résumé

We prove that every connected cubic graph with $n$ vertices has a maximal matching of size at most $\frac{5}{12} n+ \frac{1}{2}$. This confirms the cubic case of a conjecture of Baste, Fürst, Henning, Mohr and Rautenbach (2019) on regular graphs. More generally, we prove that every graph with $n$ vertices and $m$ edges and maximum degree at most $3$ has a maximal matching of size at most $\frac{4n-m}{6}+ \frac{1}{2}$. These bounds are attained by the graph $K_{3,3}$, but asymptotically there may still be some room for improvement. Moreover, the claimed maximal matchings can be found efficiently. As a corollary, we have a $\left(\frac{25}{18} + O \left( \frac{1}{n}\right)\right) $-approximation algorithm for minimum maximal matching in connected cubic graphs.

Détail

DOI : 10.37236/9963

Classification : 05C70, 05C69, 68W25
Mots-clés : connected cubic graph, maximal matchings