Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Allen, G.R.: Dimer models for the antiferroelectric transition in copper formate tetrahydrate. J. Chem. Phys. 60, 3299–3309 (1974)
Fischer, I., Little, C.H.C.: A characterization of Pfaffian near bipartite graphs. J. Comb. Theory Ser. B 82, 175–222 (2001)
Kasteleyn, P.W.: The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice. Physica 27, 1209–1225 (1961)
Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp. 43–110. Academic Press, London (1967)
Lieb, E.H., Loss, M.: Fluxes, Laplacians, and Kasteleyn’s theorem. Duke Math. J. 71, 337–363 (1993)
Little, C.H.C.: Kasteleyn’s theorem and arbitrary graphs. Can. J. Math. 25, 758–764 (1973)
Little, C.H.C.: A characterization of convertible \((0,1)\)-matrices. J. Comb. Theory Ser. B 18, 187–208 (1975)
Lovász, L., Plummer, M.D.: Matching Theory. North-Holland, Amsterdam (1986)
Lu, F.L., Zhang, L.Z.: The Pfaffian property of Cartesian products of graphs. J. Comb. Optim. 27, 530–540 (2014)
Lu, F.L., Zhang, L.Z., Wang, Y.: The Pfaffian property of circulant graphs. Discret. Appl. Math. 181, 185–192 (2015)
McCuaig, W.: Pólya’s permanent problem. Electron. J. Combin. 11(1), R79 (2004)
Nagle, J.F., Yokoi, C.S.O., Bhattacharjee, S.M.: Dimer models on an isotropic lattices. In: Domb, C., Lebowitz, J.L. (eds.) Phase Transitions and Critical Phenomena, vol. 13. Academic Press, New York (1989)
Norine, S.: Matching structure and Pfaffian orientations of graphs. Doctoral dissertation, Georgia Institute of Technology (2005)
Robertson, N., Seymour, P.D., Thomas, R.: Permanents, Pfaffian orientations and even directed circuits. Ann. Math. 2(150), 929–975 (1999)
Salinas, S.R., Nagle, J.F.: Theory of the phase transition in the layered hydrogen-bonded SnCl\(_2\cdot \)2H\(_2\)O crystal. Phys. Rev. B 9, 4920–4931 (1974)
Temperley, H.N.V., Fisher, M.E.: Dimer problem in statistical mechanics—an exact result. Philos. Mag. 6, 1061–1063 (1961)
Tesler, G.: Matchings in graphs on non-orientable surfaces. J. Comb. Theory Ser. B 78, 198–231 (2000)
Thomassen, C.: Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface. Trans. Am. Math. Soc. 323, 605–635 (1991)
Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189–201 (1979)
Zhang, L.Z., Wang, Y., Lu, F.L.: Pfaffian graphs embedding on the torus. Sci. China Math. 56, 1957–1964 (2012)
Acknowledgements
We are grateful to the anonymous referees for their careful reading and many helpful suggestions that greatly improved our original manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
The research is supported by National Natural Science Foundation of China (Grant nos. 11471273; 11671186).
Rights and permissions
About this article
Cite this article
Feng, X., Zhang, L. & Zhang, M. A Sufficient Condition for Pfaffian Graphs on the Torus. Graphs and Combinatorics 33, 1249–1260 (2017). https://doi.org/10.1007/s00373-017-1841-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-017-1841-0