|Table of Contents|

The Number of Perfect Matchings in Four Types of Particular Graphs(PDF)

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

Issue:
2013年01期
Page:
10-15
Research Field:
数学
Publishing date:

Info

Title:
The Number of Perfect Matchings in Four Types of Particular 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; linear recurrence relation; characteristic equation
PACS:
O157.5
DOI:
-
Abstract:
Matching counting theory is at the core of graph theory.Since it has important applications and is in connection with other theoretic problems closely,it has been studied extensively,and many celebrated results have been established.But the problem of counting the number of perfect matchings for general graphs is NP-hard.In this paper,by applying differentiation,summation and re-nested recursive calculation,several counting formulas of the perfect matching for four specific types of graphs are given.By the method presented in this paper,the number of all perfect matchings of many particular graphs can be calculated.

References:

[1] Kasteleyn P W.Graph Theory and Crystal Physics[M].Harary F.Graph Theory and Theoretical Physics.London:Academic Press,1967:43-110.
[2]Hall G G.A graphic model of a class of molecules[J].Int J Math Edu Sci Technol,1973,4(3):233-240.
[3]Cyvin S J,Gutman I.Keku｀Structures in Benzennoid Hydrocarbons[M].Berlin:Springer Press,1988.
[4]Ciucu M.Enumeration of perfect matchings in graphs with reflective symmetry[J].J Combin Theory Ser A,1997,77:87-97.
[5]Fischer I,Little C H C.Even circuits of prescribed clockwise parity[J].Electro J Combin,2003,10:1-20.
[6]Jockusch W.Perfect mathings and perfect squares[J].J Combin Theory Ser A,1994,67:100-115.
[7]Kasteleyn P W.Dimmer statistics and phase transition[J].Journal of Mathematical Physics,1963,4:287-293.
[8]Lovász L,Plummer M.Matching Theory[M].New York:North-Holland Press,1986.
[9]于青林,刘桂真.图的因子和匹配可扩性[M].北京:高等教育出版社,2010.
[10]Zhang Heping.The connectivity of ansformation graphs of perfect matchings of polyominoes[J].Discrete Mathematics,1996,158:257-272.
[11]Zhang Heping,Zhang Fuji.Perfect matchings of polyomino graphs[J].Graphs and Combinatorics,1997,13:259-304.
[12]张莲珠.渺位四角系统完美匹配数的计算[J].厦门大学学报:自然科学版,1998,37(5):629-633.
[13]林泓,林晓霞.若干四角系统完美匹配数的计算[J].福州大学学报:自然科学版,2005,33(6):704-710.
[14]Yan Weigen,Zhang Fuji.Enumeration of perfect matchings of a type of Cartesian products of graphs[J].Discrete Applied Mathematics,2006,154:145-157.
[15]唐保祥,任韩.几类图完美匹配的数目[J].南京师大学报:自然科学版,2010,33(3):1-6.
[16]唐保祥,李刚,任韩.3类图完美匹配的数目[J].浙江大学学报:理学版,2011,38(4):16-19.
[17]唐保祥,任韩.2类图完美匹配的数目[J].西南师范大学学报:自然科学版,2011,36(5):16-21.
[18]唐保祥,任韩.3类图完美匹配的计数[J].南京师大学报:自然科学版,2012,35(1):16-21.
[19]唐保祥,任韩.6类图完美匹配的数目[J].中山大学学报:自然科学版,2012,51(1):40-44.

Memo

Memo:
-
Last Update: 2013-03-31