Graphical condensation of plane graphs: A combinatorial approach

摘要

The method of graphical vertex-condensation for enumerating perfect matchings of plane bipartite graph was found by Propp [Generalized Domino-shuffling, Theoret. Comput. Sci. 303 (2003) 267-301], and was generalized by Kuo [Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004) 29-57] and Yan and Zhang [Graphical condensation for enumerating perfect matchings, J. Combin, Theory Ser. A 110 (2005) 113-125]. In this paper, by a purely combinatorial method some explicit identities on graphical vertex-condensation for enumerating perfect matchings of plane graphs (which do not need to be bipartite) are obtained. As applications of our results, some results on graphical edge-condensation for enumerating perfect matchings are proved, and we count the sum of weights of perfect matchings of weighted Aztec diamond.