|Table of Contents|

The Number of Perfect Matching in Several Types of Graphs(PDF)

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

Issue:
2010年03期
Page:
1-6
Research Field:
数学
Publishing date:

Info

Title:
The Number of Perfect Matching in Several Types of Graphs
Author(s):
Tang Baoxiang1; 2; Ren Han2
1.School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,China 2. Department of M athem atics, E ast Ch in a Norm alU n ivers ity, Shanghai 200062, China
Keywords:
linea r recurrence re lation;  perfect m atch ing;  H am ilton cy cle;  edge cut
PACS:
O157.5
DOI:
-
Abstract:
Enum eration of perfect m atchings o f graphs is an im portan t sub ject in the m atch ing theo ry. It is much re la ted w ith statistica l physics o f cry sta l d imm er issue. But the enum era tion problem for perfect m atchings in g eneral g raphs is NP-hard. The explic it fo rmu lae for the number o f the pe rfectm atching in som e types o f g raphs a re deduced. As an app l-i ca tion, the number o fH am ilton cycles o f som e g raphs has been ca lculated.

References:

[ 1] Bondy J A, Murty U S R. 吴望名, 李念祖, 吴兰芳, 等译. 图论及其应用[M ]. 北京: 科学出版社, 1984.
[ 2] H a ll G G. A g raph ic mode l o f a c lass o fm o lecules[ J]. Int JM a th Edu Sc,i 1973, 4: 233-240.
[ 3] Pauling L. TheN ature o f Chem ica l Bond, Co rnell[M ]. Ithaca: Un iv Press, 1939.
[ 4] Cyv in S J, Gutm an I. Kekul struc tures in Benzenno id hydrocarbons[M ] . Berlin: Spr inger Press, 1988.
[ 5] Kaste leyn PW. Graph theory and cry sta l physics[M ] / / H ara ry F. Graph Theory and Theoretica l Phy sics. London: A cademic Press, 1967: 43-110.
[ 6] Lov sz L, P lumm e rM. M atching Theory[M ]. New Yo rk: North-H o lland Press, 1986.
[ 7] C iucuM. Enum eration of perfect m atchings in g raphs w ith re flective symm etry[ J]. J Comb in Theory Ser A, 1997, 77: 87- 97.
[ 8] Fische r I, L ittle C H C. Even circu its of prescr ibed clockw ise par ity [ J/OL] . E lec tro J Com b in, 2003, 10 [ 2010-04-20]. http: / /www. em is. am s. o rg / journals/E JC /Vo lum e- 10 /PDF /V1o i1r45. pdf
[ 9] JockuschW. Perfect m ath ings and perfect squa res[ J] . J Comb in Theory Ser A, 1994, 67: 100-115.
[ 10] Br ightw ellG R, W ink le r P, H ard C, et a.l Adventures at the interface o f com bina to ries and sta tistica l phy sics[ J]. ICM, 2002, III: 605-624.
[ 11] Zhang H P. The connectiv ity of Z- transform ation graphs o f perfec t m atchings o f polyom inoes[ J]. D iscrete M athema tics, 1996, 158: 257-272.
[ 12] Zhang H P, Zhang F J. Perfect m atchings of po lyom ino graphs[ J]. G raphs and Com binato rics, 1997, 13: 259-304.
[ 13] 张莲珠. 渺位四角系统完美匹配数的计算[ J]. 厦门大学学报: 自然科学版, 1998, 37( 5): 629-633.
[ 14] 张莲珠. 两类四角系统的匹配数与点独立集数[ J]. 数学研究, 1999, 32( 3) : 97-102.
[ 15] 林泓, 林晓霞. 若干四角系统完美匹配数的计算[ J]. 福州大学学报: 自然科学版, 2005, 33( 6): 704-710.

Memo

Memo:
-
Last Update: 2013-04-08