论文标题
立方图中的最小最大匹配
Minimum maximal matchings in cubic graphs
论文作者
论文摘要
我们证明，每个与$ n $ VERTICES的连接的立方图最多都具有最大匹配，最多最多$ \ frac {5} {12} {12} n+ \ frac {1} {2} {2} $。这证实了baste，fürst，Henning，Mohr和Rautenbach（2019）在常规图上的立方体案例。更笼统地，我们证明，每个图表具有$ n $顶点和$ M $边缘，最多最高$ 3 $都具有最大尺寸的最大匹配，最多$ \ frac {4n-m} {6} {6}+ \ frac {1} {1} {2} {2} $。这些界限是由图$ k_ {3,3} $实现的，但是渐近地可能还有一些改进的空间。此外，可以有效地找到所声称的最大匹配。作为推论，我们有一个$ \ left（\ frac {25} {18} + o \ left（\ frac {1} {n} {n} \ right）\ right）$ - approximation算法，用于最小值最大值的最大值。
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.
