| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10334269 | Theoretical Computer Science | 2005 | 10 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Weigen Yan, Yeong-Nan Yeh, Fuji Zhang,