Minimum maximal matchings in cubic graphs
share
We prove that every connected cubic graph with n vertices has a maximal matching of size at most 5/12 n+ 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 4n-m/6+ 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 (25/18 + O ( 1/n))-approximation algorithm for minimum maximal matching in connected cubic graphs.
READ FULL TEXT