[1]唐保祥,任 韩.2类图的完美匹配数的分类递推求法[J].南京师范大学学报(自然科学版),2019,42(01):1.[doi:10.3969/j.issn.1001-4616.2019.01.001]
　Tang Baoxiang,Ren Han.Classification and Push Solution Method for the Number ofPerfect Matchings of Two Types Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2019,42(01):1.[doi:10.3969/j.issn.1001-4616.2019.01.001]
点击复制

2类图的完美匹配数的分类递推求法()
分享到：

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

卷:
第42卷
期数:
2019年01期
页码:
1
栏目:
·数学·
出版日期:
2019-03-20

文章信息/Info

Title:
Classification and Push Solution Method for the Number ofPerfect Matchings of Two Types Graphs
文章编号:
1001-4616(2019)01-0001-05
作者:
唐保祥1; 任 韩2
(1.天水师范学院数学与统计学院,甘肃 天水 741001)(2.华东师范大学数学系,上海 200062)
Author(s):
Tang Baoxiang1; Ren Han2
(1.School of Mathematics and Statistics Institute,Tianshui Normal University,Tianshui 741001,China)(2.Department of Mathematics,East China Normal University,Shanghai 200062,China)
关键词:
完美匹配; 递推式关系; 通解; 显式公式
Keywords:
perfect matching; recurrence formula; general solution; explicit formula
分类号:
O157.5
DOI:
10.3969/j.issn.1001-4616.2019.01.001
文献标志码:
A
摘要:
首先,把图的完美匹配按关联某个顶点的边进行分类,求出每一类完美匹配数目的递推关系式.其次,把各类完美匹配的递推式相加,得到一组有相互联系的递推关系式,再利用这些递推式之间的相互关联,消去那些不需要的递推关系式,从而得到这个图的完美匹配数目的递推关系式.最后解出这个递推式的通解,进而得到这个图的完美匹配数目的显式公式.
Abstract:
Firstly,the perfect matching of the graph is classified according to the edge associated with a certain vertex,and the recursive relation of each type of perfect matching is obtained. Secondly,the recursive sums of the perfect matching are added to obtain a set of mutual recursive relation of the contact,and then use the reciprocal relationship between these recursive methods to eliminate the recursive relations that are not needed,so as to obtain the recursive relation of the perfect matching number of the graph. Finally,the recursive formula is solved. The general solution,and then get the explicit formula of the perfect matching number of this graph.

参考文献/References:

[1] ZHANG H P. The connectivity of Z-transformation graphs of perfect matchings of polyominoes[J]. Discrete mathematics,1996,158:257-272.
[2]ZHANG H P,ZHANG F J. Perfect matchings of polyomino graphs[J]. Graphs and combinatorics,1997,13:259-304.
[3]LI S L,YAN W G. The matching energy of graphs with given parameters[J]. Discrete applied mathematics,2014,162:415-420.
[4]DONG F M,YAN W G,ZHANG F J. On the number of perfect matchings of line graphs[J]. Discrete applied mathematics,2013,161:794-801.
[5]YAN WG,ZHANG F J. A quadratic identity for the number of perfect matchings of plane graphs[J]. Theoretical computer science,2008,409:405-410.
[6]CHANG A,TIAN F,YU A M. On the index of bicyclic graphs with perfect matchings[J]. Discrete mathematics,2004,283:51-59.
[7]CHANG A,SHIU W C. On the kth eigenvalues of trees with perfect matchings[J]. Discrete mathematics and theoretical computer science,2007,9(1):321-332.
[8]唐保祥,任韩. 两类图完美匹配的计数公式[J]. 吉林大学学报(理学版),2016,54(4):790-792.
[9]唐保祥,任韩. 2类图完美匹配数目的解析式[J]. 中山大学学报(自然科学版),2016,55(4):15-17.
[10]唐保祥,任韩. 4 类图完美匹配数目的递推求法[J]. 数学杂志,2015,353(2):626-634.
[11]唐保祥,任韩. 几类图完美匹配的数目[J]. 南京师大学报(自然科学版),2010,33(3):1-6.

相似文献/References:

[1]唐保祥,任韩.3类图完美匹配的计数[J].南京师范大学学报(自然科学版),2012,35(01):16.
　Tang Baoxiang,Ren Han.The Number of Perfect Matchings in Three Types of Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2012,35(01):16.
[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]
[4]唐保祥,任韩.2类图完美匹配数目解析式的嵌套递推求法[J].南京师范大学学报(自然科学版),2020,43(01):1.[doi:10.3969/j.issn.1001-4616.2020.01.001]
　TangBaoxiang,RenHan.TheNestedRecursiveMethodofAnalyticFormulaoftheNumberofPerfectMatchingsforTwoTypesofGraphs[J].Journal of Nanjing Normal University(Natural Science Edition),2020,43(01):1.[doi:10.3969/j.issn.1001-4616.2020.01.001]
[5]唐保祥,任 韩.2类特殊图的完美对集数的分类递推求法[J].南京师范大学学报(自然科学版),2021,44(01):1.[doi:10.3969/j.issn.1001-4616.2021.01.001]
　Tang Baoxiang,Ren Han.Classification and Recursive Method for Perfect MatchingNumber of Two Kinds of Special Graphsc[J].Journal of Nanjing Normal University(Natural Science Edition),2021,44(01):1.[doi:10.3969/j.issn.1001-4616.2021.01.001]

备注/Memo

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