|Table of Contents|

Counting Formulas of the Number of Perfect Matchings ofthe Three Types of Graphs(PDF)

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

Issue:
2016年04期
Page:
0-
Research Field:
·数学与计算机科学·
Publishing date:

Info

Title:
Counting Formulas of the Number of Perfect Matchings ofthe Three Types of Graphs
Author(s):
Tang Baoxiang1; Ren Han2
(1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China)(2.Department of Mathematics,East China Normal University,Shanghai 200062,China)
Keywords:
perfect matching; ladder; linear recurrence relation; characteristic equation
PACS:
O157.5
DOI:
10.3969/j.issn.1001-4616.2016.04.001
Abstract:
Perfect matching counting problems graph has been proven to be NP-hard,so to get the number of perfectly matched general graph is very difficult. The issue has important applications in protein structure prediction,quantum chemistry,crystal physics and computer science. Research on this issue has very important theoretical and practical significance. The counting formula of the perfect matching for graphs 2-nT2,1-nDT2 and 3-nDT4 is made by applying differentiation,summation and re-recursion in this paper. By the method presented in this paper,the number of all perfect matchings of many graphs can be calculated.

References:

[1] LOV SZ L,PLUMMER M. Matching theory[M]. New York:North-Holland Press,1986.
[2]ZHANG H P. The connectivity of ansformation graphs of perfect matchings of polyominoes[J]. Discrete mathematics,1996,158:257-272.
[3]林泓,林晓霞.若干四角系统完美匹配数的计算[J]. 福州大学学报(自然科学版),2005,33(6):704-710.
[4]YAN W G,ZHANG F J. Enumeration of perfect matchings of a type of Cartesian products of graphs[J]. Discrete applied mathematics,2006,154:145-157.
[5]唐保祥,任韩. 4类图完美匹配数目的递推求法[J]. 数学杂志,2015,353(2):626-634.
[6]唐保祥,任韩. 3类特殊图完美对集数的计算[J]. 南开大学学报(自然科学版),2014,47(5):11-16.
[7]唐保祥,任韩. 4类图完美匹配的计数[J]. 武汉大学学报(理学版),2012,58(5):441-446.
[8]唐保祥,李刚,任韩. 3类图完美匹配的数目[J]. 浙江大学学报(理学版),2011,38(4):16-19.
[9]唐保祥,任韩. 5类特殊图完美的计数[J]. 山西大学学报(自然科学版),2013,36(1):18-24.
[10]唐保祥,任韩. 两类3 正则图中的完美匹配数[J]. 中山大学学报(自然科学版),2014,53(5):54-58.
[11]唐保祥,任韩. 3类图完美匹配的计数[J]. 南京师大学报(自然科学版),2012,35(1):16-21.

Memo

Memo:
-
Last Update: 2016-12-31