Minimum maximal matchings in cubic graphs

Abstract

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.

arXiv comment16 pages, 3 figures. Revised based on referees' comments