An orientation of a graph G with even number of vertices is Pfaffian if every even cycle C such that G-V(C) has a perfect matching has an odd number of edges directed in either direction of the cycle. The significance...An orientation of a graph G with even number of vertices is Pfaffian if every even cycle C such that G-V(C) has a perfect matching has an odd number of edges directed in either direction of the cycle. The significance of Pfaffian orientations stems from the fact that if a graph G has one, then the number of perfect matchings of G can be computed in polynomial time. There is a classical result of Kasteleyn that every planar graph has a Pfaffian orientation. Little proved an elegant characterization of bipartite graphs that admit a Pfaffian orientation. Robertson, Seymour and Thomas (1999) gave a polynomial-time recognition algorithm to test whether a bipartite graph is Pfaffian by a structural description of bipartite graphs. In this paper, we consider the Pfaffian property of graphs embedding on the orientable surface with genus one (i.e., the torus). Some sufficient conditions for Pfaffian graphs on the torus are obtained. Furthermore, we show that all quadrilateral tilings on the torus are Pfaffian if and only if they are not bipartite graphs.展开更多
基金National Natural Science Foundation of China (Grant Nos. 10831001 and 11171279)the Scientific Research Foundation of Zhangzhou Normal University (Grant No. SX1002)
文摘An orientation of a graph G with even number of vertices is Pfaffian if every even cycle C such that G-V(C) has a perfect matching has an odd number of edges directed in either direction of the cycle. The significance of Pfaffian orientations stems from the fact that if a graph G has one, then the number of perfect matchings of G can be computed in polynomial time. There is a classical result of Kasteleyn that every planar graph has a Pfaffian orientation. Little proved an elegant characterization of bipartite graphs that admit a Pfaffian orientation. Robertson, Seymour and Thomas (1999) gave a polynomial-time recognition algorithm to test whether a bipartite graph is Pfaffian by a structural description of bipartite graphs. In this paper, we consider the Pfaffian property of graphs embedding on the orientable surface with genus one (i.e., the torus). Some sufficient conditions for Pfaffian graphs on the torus are obtained. Furthermore, we show that all quadrilateral tilings on the torus are Pfaffian if and only if they are not bipartite graphs.
