Graphical condensation for enumerating perfect matchings

DOI10.1016/j.jcta.2004.10.005zbMath1059.05087MaRDI QIDQ1775549

Weigen Yan, Fu Ji Zhang

Publication date: 4 May 2005

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcta.2004.10.005

zbMATH Keywords

Aztec diamond; Perfect matching; Symmetric graph; Graphical condensation; Plane partition

Mathematics Subject Classification ID

05A15: Exact enumeration problems, generating functions

05A18: Partitions of sets

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

The characteristic polynomial and the matchings polynomial of a weighted oriented graph, Generalizing the divisibility property of rectangle domino tilings, Graphical condensation of plane graphs: a combinatorial approach, Proof of two conjectures of Ciucu and Krattenthaler on the enumeration of lozenge tilings of hexagons with cut off corners, A quadratic identity for the number of perfect matchings of plane graphs, Replacing Pfaffians and applications, A new simple proof of the Aztec diamond theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Applications of graphical condensation for enumerating matchings and tilings
• Alternating-sign matrices and domino tilings. I
• Dodgon's determinant-evaluation rule proved by TWO-TIMING MEN and WOMEN
• A complementation theorem for perfect matchings of graphs having a cellular completion
• Generalized domino-shuffling.
• Perfect matchings of cellular graphs
• Enumeration of perfect matchings in graphs with reflective symmetry