Minimum maximal matchings in cubic graphs (Q2144321)

Summary: 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 \textit{J. Baste} et al. [Discrete Math. 344, No. 3, Article ID 112243, 8 p. (2021; Zbl 1458.90537)] 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.