次三正则图最小极大匹配上界的改进

Improvement of Upper Bound of Minimum Maximal Matching in Subcubic Graphs

摘要: 图G的边控制数是图中最大匹配的最小大小。众所周知，这个参数计算起来很困难。Julien Baste根据正则图和非正则图的阶数及最大度给出了最优可能上界。研究了边支配数的上界和相关算法，他给出了次三正则二部不含T*图的最小极大匹配的上界。其中T^*是由爪形图的两条边恰好细分一次而形成的树。本文在此基础上，改进了其中次三正则图边控制数的上界，并作出一些推论。

Abstract: The edge control number Υ(G) of graph G is the minimum size of a maximal match in the graph. This parameter is notoriously difficult to calculate. Julien Baste gives the optimal possible upper bound according to the order and maximum degree of regular graph and non-regular graph. In this paper, we study the upper bound and correlation algorithm of edge dominating numbers. He gives the upper bound of minimum maximal matching of subcubic bipartite T*-free graph, where T* is the tree formed by subdividing the two edges of the claw graph exactly once. On this basis, we improve the upper bound of the edge control numbers of the subcubic graphs, and make some inferences.