A Sufficient Condition for Pfaffian Graphs on the Torus

作者：Feng, Xing; Zhang, Lianzhu^*; Zhang, Mingzu

来源：Graphs and Combinatorics, 2017, 33(5): 1249-1260.

DOI：10.1007/s00373-017-1841-0

• Pfaffian graphs
• The sign of perfect matchings
• Graphs embedding on the torus

The significance of Pfaffian orientations stems from the fact that if a graph has such an orientation, then the number of perfect matchings (as known as the dimer problem) can be computed in polynomial time. A graph is called Pfaffian if it has a Pfaffian orientation. The Pfaffian property of a graph is not well-characterized. We do not even know whether the property of an undirected graph that it has a Pfaffian orientation is in NP. In this paper, we consider Pfaffian graphs on torus. More specific, we prove that for a non-bipartite graph embedding on the torus, if the boundaries of all faces are even, then it is Pfaffian.

• 出版日期2017-9
• 单位厦门大学