[1]唐保祥,任 韩.3类3-正则图中的完美对集数[J].南京师范大学学报(自然科学版),2016,39(01):21.
 Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Two Types of 3-Regular Graph[J].Journal of Nanjing Normal University(Natural Science Edition),2016,39(01):21.
点击复制

3类3-正则图中的完美对集数()
分享到:

《南京师范大学学报》(自然科学版)[ISSN:1001-4616/CN:32-1239/N]

卷:
第39卷
期数:
2016年01期
页码:
21
栏目:
数学
出版日期:
2016-03-31

文章信息/Info

Title:
The Number of Perfect Matchings in Two Types of 3-Regular Graph
作者:
唐保祥1任 韩2
(1.天水师范学院数学与统计学院,甘肃 天水 741001)(2.华东师范大学数学系,上海 200062)
Author(s):
Tang Baoxiang1Ren Han2
(1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China)(2.Department of Mathematics,East China Normal University,Shanghai 200062,China)
关键词:
完美对集线性递推式2-边连通图3-正则图
Keywords:
perfect matchinglinear recurrence relation2-edge connected3-regular graph
分类号:
O157.5
文献标志码:
A
摘要:
Lovász L和Plummer M 提出了一个猜想:任意2-边连通图至少有指数多个完美对集. 这个猜想至今没有被证明,也没有被否定. 本文用划分、求和,再嵌套递推的方法给出了3类特殊图完美对集数目的显式表达式,从而验证了Lovász L和Plummer M猜想在这3类图上的正确性.
Abstract:
Lovász and Plummer proposed a conjecture on this problem:every 2-edge-connected cubic graph has at least exponential 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 types of graphs are given. And the results indicate that the conjecture of Lovász and Plummer conjecture is true in the case of the three types of graphs.

参考文献/References:

[1] LOVáSZ L,PLUMMER M. Matching Theory[M]. New York:North-Holland Press,1986.

[2] KRáL D,SERENI J S,STIEBITZ M. A new lower bound on the number of perfect matchings in cubic graphs[J]. Discrete Math,2009,23:1 465-1 483.
[3] KARDOS F,KRáL D,MISKUF J,et al. Fullerene graphs have exponentially many perfect matchings[J]. Journal of Mathematical Chemistry,2009,46:443-447.
[4] 唐保祥,任韩. 几类图完美匹配的数目[J]. 南京师大学报(自然科学版),2010,33(3):1-6.

相似文献/References:

[1]唐保祥.几类图完美匹配的数目[J].南京师范大学学报(自然科学版),2010,33(03):1.
 Tang Baoxiang,Ren Han.The Number of Perfect Matching in Several Types of Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2010,33(01):1.
[2]唐保祥,任 韩.4类特殊图完美匹配的计数[J].南京师范大学学报(自然科学版),2013,36(01):10.
 Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Four Types of Particular Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2013,36(01):10.
[3]唐保祥,任 韩.3类图完美匹配数目的计算公式[J].南京师范大学学报(自然科学版),2016,39(04):0.[doi:10.3969/j.issn.1001-4616.2016.04.001]
 Tang Baoxiang,Ren Han.Counting Formulas of the Number of Perfect Matchings ofthe Three Types of Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2016,39(01):0.[doi:10.3969/j.issn.1001-4616.2016.04.001]

备注/Memo

备注/Memo:
收稿日期:2015-03-17. 
基金项目:国家自然科学基金项目(11171114). 
通讯联系人:唐保祥,教授,研究方向:图论和组合数学. E-mail:tbx0618@sina.com
doi:10.3969/j.issn.1001-4616.2016.01.003
更新日期/Last Update: 2016-03-30