Matchings in graphs on non-orientable surfaces

被引:91
作者
Tesler, G [1 ]
机构
[1] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
关键词
Perfect matching; graph; dimer; Kasteleyn; Pfaffian;
D O I
10.1006/jctb.1999.1941
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:198 / 231
页数:34
相关论文
共 50 条
  • [31] Perfect Matchings of Regular Bipartite Graphs
    Lukot'ka, Robert
    Rollova, Edita
    JOURNAL OF GRAPH THEORY, 2017, 85 (02) : 525 - 532
  • [32] On the Perfect Matchings of Near Regular Graphs
    Xinmin Hou
    Graphs and Combinatorics, 2011, 27 : 865 - 869
  • [33] Perfect matchings in pruned grid graphs
    Guichard, David R.
    DISCRETE MATHEMATICS, 2008, 308 (24) : 6552 - 6557
  • [34] Graphs with second smallest number of perfect matchings of line graphs
    Liu, Yan
    Zhou, Xue
    ARS COMBINATORIA, 2020, 153 : 15 - 31
  • [35] Rainbow matchings in Dirac bipartite graphs
    Coulson, Matthew
    Perarnau, Guillem
    RANDOM STRUCTURES & ALGORITHMS, 2019, 55 (02) : 271 - 289
  • [36] Fullerene graphs with exponentially many perfect matchings
    Doslic, Tomislav
    JOURNAL OF MATHEMATICAL CHEMISTRY, 2007, 41 (02) : 183 - 192
  • [37] Perfect Matchings in Edge-Transitive Graphs
    Marandi, A.
    Nejah, A. H.
    Behmaram, A.
    IRANIAN JOURNAL OF MATHEMATICAL CHEMISTRY, 2014, 5 : S27 - S33
  • [38] Constrained weighted matchings and edge coverings in graphs
    Plesník, J
    DISCRETE APPLIED MATHEMATICS, 1999, 92 (2-3) : 229 - 241
  • [39] Matchings in m-generalized fullerene graphs
    Behmaram, Afshin
    Doslic, Tomislav
    Friedland, Shmuel
    ARS MATHEMATICA CONTEMPORANEA, 2016, 11 (02) : 301 - 313
  • [40] Perfect Matchings in Total Domination Critical Graphs
    Michael A. Henning
    Anders Yeo
    Graphs and Combinatorics, 2011, 27 : 685 - 701