3类3-正则图中的完美对集数  

The Number of Perfect Matchings in Two Types of 3-Regular Graph

作　　者：唐保祥[1] 任韩[2] 

机构地区：[1]天水师范学院数学与统计学院,甘肃天水741001 [2]华东师范大学数学系,上海200062

出　　处：《南京师大学报（自然科学版）》2016年第1期21-24,共4页Journal of Nanjing Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(11171114)

摘　　要：Lovász L和Plummer M提出了一个猜想:任意2-边连通图至少有指数多个完美对集.这个猜想至今没有被证明,也没有被否定.本文用划分、求和,再嵌套递推的方法给出了3类特殊图完美对集数目的显式表达式,从而验证了Lovász L和Plummer M猜想在这3类图上的正确性.Lovász and Plummer proposed a conjecture on this problem：every 2-edge-connected cubic graph has at leastexponential perfect matchings. This conjecture has not been proved or denied. In this paper,by applying differentiation,summation and the re-nested recursive method,several counting formulas of the perfect matching for three specific typesof graphs are given. And the results indicate that the conjecture of Lovász and Plummer conjecture is true in the case ofthe three types of graphs.

关 键 词：完美对集 线性递推式 2-边连通图 3-正则图 

分 类 号：O157.5[理学—数学]