4类特殊图完美匹配的计数

摘要：

匹配计数理论是图论的核心内容之一,由于得到应用领域的支持,并与其他理论课题发生密切联系,受到众多学者的关注,产生出许多含义丰富而深刻的理论成果.但是,一般图的完美匹配计数问题却是NP-难问题.本文用划分、求和、再嵌套递推的方法给出了4类图完美匹配数目的显式表达式,所给出的方法,可以计算出许多特殊图的所有完美匹配的数目.

关键词：完美匹配、线性递推式、特征方程

所属期刊栏目：36

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金11171114

在线出版日期：2013-05-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：10-15