We generalize Kasteleyn's method of enumerating the perfect matchings in a planar graph to graphs embedding on an arbitrary compact boundaryless 2-manifold S. Kasteleyn stated that perfect matchings in a graph embedding on a surface of genus g could be enumerated as a linear combination of 4(g) Pfaffians of modified adjacency matrices of the graph. We give an explicit construction that not only does this, but also does it for graphs embedding on non-orientable surfaces. If a graph embeds on the connected sum of a genus g surface with a projective plane (respectively, Klein bottle), the number of perfect matchings can be computed as a linear combination of 2(2g + 1) (respectively, 2(2g +2)) Pfaffians. Thus for any S, this is 2(2-x(S)) Pfaffians. We also introduce "crossing orientations," the analogue of Kasteleyn's "admissible orientations" in our context, describing how the Pfaffian of a signed adjacency matrix of a graph gives the sign of each perfect matching according to the number of edge-crossings in the matching. Finally, we count the perfect matchings of an m x n grid on a Mobius strip. (C) 2000 Academic Press.
机构:
South China Normal Univ, Sch Math Sci, Guangzhou 510631, Guangdong, Peoples R ChinaSouth China Normal Univ, Sch Math Sci, Guangzhou 510631, Guangdong, Peoples R China
Liu, Yan
Zhou, Xue
论文数: 0引用数: 0
h-index: 0
机构:
South China Normal Univ, Sch Math Sci, Guangzhou 510631, Guangdong, Peoples R ChinaSouth China Normal Univ, Sch Math Sci, Guangzhou 510631, Guangdong, Peoples R China
机构:
Univ Tabriz, Fac Math Sci, Tabriz, Iran
Inst Res Fundamental Sci IPM, Sch Math, POB 19395-5746, Tehran, IranUniv Tabriz, Fac Math Sci, Tabriz, Iran
Behmaram, Afshin
Doslic, Tomislav
论文数: 0引用数: 0
h-index: 0
机构:
Fac Civil Engn, Kaciceva 26, Zagreb 10000, CroatiaUniv Tabriz, Fac Math Sci, Tabriz, Iran
Doslic, Tomislav
Friedland, Shmuel
论文数: 0引用数: 0
h-index: 0
机构:
Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60607 USAUniv Tabriz, Fac Math Sci, Tabriz, Iran
机构:
South China Normal Univ, Sch Math Sci, Guangzhou 510631, Guangdong, Peoples R ChinaSouth China Normal Univ, Sch Math Sci, Guangzhou 510631, Guangdong, Peoples R China
Liu, Yan
Zhou, Xue
论文数: 0引用数: 0
h-index: 0
机构:
South China Normal Univ, Sch Math Sci, Guangzhou 510631, Guangdong, Peoples R ChinaSouth China Normal Univ, Sch Math Sci, Guangzhou 510631, Guangdong, Peoples R China
机构:
Univ Tabriz, Fac Math Sci, Tabriz, Iran
Inst Res Fundamental Sci IPM, Sch Math, POB 19395-5746, Tehran, IranUniv Tabriz, Fac Math Sci, Tabriz, Iran
Behmaram, Afshin
Doslic, Tomislav
论文数: 0引用数: 0
h-index: 0
机构:
Fac Civil Engn, Kaciceva 26, Zagreb 10000, CroatiaUniv Tabriz, Fac Math Sci, Tabriz, Iran
Doslic, Tomislav
Friedland, Shmuel
论文数: 0引用数: 0
h-index: 0
机构:
Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60607 USAUniv Tabriz, Fac Math Sci, Tabriz, Iran