|Table of Contents|

TheNestedRecursiveMethodofAnalyticFormulaoftheNumberofPerfectMatchingsforTwoTypesofGraphs(PDF)

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

Issue:
2020年01期
Page:
1-4
Research Field:
·数学·
Publishing date:

Info

Title:
TheNestedRecursiveMethodofAnalyticFormulaoftheNumberofPerfectMatchingsforTwoTypesofGraphs
Author(s):
TangBaoxiang1; RenHan2
(1.SchoolofMathematicsandStatistics,TianshuiNormalUniversity,Tianshui741001,China)(2.DepartmentofMathematics,EastChinaNormalUniversity,Shanghai200062,China)
Keywords:
perfectmatching; linearrecurrencerelation; characteristicequation
PACS:
O175.5
DOI:
10.3969/j.issn.1001-4616.2020.01.001
Abstract:
It’simportantapplyforperfectmatchingcountingtheoriesincrystalphysics,quantumchemistryandcomputerscience.Theresearchforperfectmatchingcountingshasaquiteimportanttheoreticalvalueandrealisticmeanings.However,thecountingproblemofperfectmatchingsforgeneralgraphshasbeenprovedtobeNP-hard.Inthispaper,byapplyingdifferentiation,summationandre-nestedrecursivecalculation,severalcountingformulaeoftheperfectmatchingsfortwospecifictypesofgraphsaregiven.Therefore,thisprovidesthetheorysupportfortheapplicationofperfectmatchingingraphs.

References:

[1]VALIANTLG.Thecomplexityofcomputingthepermanent[J].Theoreticalcomputescience,1979,8(2):189-201.
[2]LOVáSZL,PLUMMERM.Matchingtheory[M].NewYork:North-HollandPress,1986.
[3]YANWG,ZHANGFJ.Enumerationofperfectmatchingsofatypeofcartesianproductsofgraphs[J].Discreteappliedmathematics,2006,154:145-157.
[4]LISL,YANWG.Thematchingenergyofgraphswithgivenparameters[J].Discreteappliedmathematics,2014,162:415-420.
[5]DONGFM,YANWG,ZHANGFJ.Onthenumberofperfectmatchingsoflinegraphs[J].Discreteappliedmathematics,2013,161:794-801.
[6]林泓,林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报(自然科学版),2005,33(6):704-710.
[7]蓝雯飞,邢志宝,黄俊,等.DNA自组装计算模型求解二部图完美匹配问题[J].计算机研究与发展,2016,53(11):2583-2592.
[8]唐保祥,任韩.4类图完美匹配数目的递推求法[J].数学杂志,2015,353(2):626-634.
[9]唐保祥,任韩.3类特殊图完美对集数的计算[J].南开大学学报(自然科学版),2014,47(5):11-16.
[10]唐保祥,任韩.2类特殊图中的完美匹配数[J].浙江大学学报(理学版),2017,44(3):266-269.
[11]唐保祥,任韩.2类图完美匹配的计数公式[J].吉林大学学报(理学版),2016,54(4):790-792.
[12]唐保祥,任韩.2类图完美匹配数目的解析式[J].中山大学学报(自然科学版),2016,55(4):15-17.
[13]唐保祥,任韩.2类特殊图中的完美匹配数[J].浙江大学学报(理学版),2017,44(3):266-269.
[14]唐保祥,任韩.3类图完美匹配数目的计数公式[J].南京师大学报(自然科学版),2016,39(4):1-3.
[15]唐保祥,任韩.4类特殊图完美匹配的计数[J].南京师大学报(自然科学版),2013,36(1):9-15.

Memo

Memo:
-
Last Update: 2020-03-15