|Table of Contents|

Classification and Push Solution Method for the Number ofPerfect Matchings of Two Types Graphs(PDF)

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

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

Info

Title:
Classification and Push Solution Method for the Number ofPerfect Matchings of Two Types Graphs
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
PACS:
O157.5
DOI:
10.3969/j.issn.1001-4616.2019.01.001
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.

Memo

Memo:
-
Last Update: 2019-03-30