Pfaffian graphs embedding on the torus  

作　　者：ZHANG LianZhu WANG Yan LU FuLiang 

机构地区：[1]School of Mathematical Sciences,Xiamen University [2]School of Sciences,Linyi University

出　　处：《Science China Mathematics》2013年第9期1957-1964,共8页中国科学：数学（英文版）

基　　金：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.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.

关 键 词：Pfaffian graph perfect matching crossing orientation 

分 类 号：O157.5[理学—数学]