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

摘要

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