Graphical condensation of plane graphs: a combinatorial approach
From MaRDI portal
Publication:817820
DOI10.1016/J.TCS.2005.09.039zbMATH Open1086.05066arXivmath/0509337OpenAlexW1974219541MaRDI QIDQ817820FDOQ817820
Authors: Weigen Yan, Yeong-Nan Yeh, Fuji Zhang 
Publication date: 20 March 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: The method of graphical vertex-condensation for enumerating perfect matchings of plane bipartite graph was found by Propp (Theoret. Comput. Sci. 303(2003), 267-301), and was generalized by Kuo (Theoret. Comput. Sci. 319 (2004), 29-57) and Yan and Zhang (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.
Full work available at URL: https://arxiv.org/abs/math/0509337
Recommendations
- Graphical condensation for enumerating perfect matchings
- Applications of graphical condensation for enumerating matchings and tilings
- A quadratic identity for the number of perfect matchings of plane graphs
- A generalization of Kuo condensation
- Graphical condensation, overlapping Pfaffians and superpositions of matchings
Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Alternating-sign matrices and domino tilings. I
- Generalized domino-shuffling.
- A simple proof of the Aztec diamond theorem
- Title not available (Why is that?)
- Enumeration of perfect matchings in graphs with reflective symmetry
- Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers
- Applications of graphical condensation for enumerating matchings and tilings
- Graphical condensation for enumerating perfect matchings
- Overlapping Pfaffians
- Pfaffian identities: A combinatorial approach
- A complementation theorem for perfect matchings of graphs having a cellular completion
- Perfect matchings of cellular graphs
- Pfaffian forms and \(\Delta\)-matroids
- A simple proof of an identity concerning Pfaffians of skew symmetric matrices
Cited In (21)
- A generalization of Kuo condensation
- A new expression for matching polynomials
- Enumeration of perfect matchings in graphs with reflective symmetry
- Weighted Aztec diamond graphs and the Weyl character formula
- Proof of a conjecture of Kenyon and Wilson on semicontiguous minors
- Applications of graphical condensation for enumerating matchings and tilings
- A \(q\)-enumeration of lozenge tilings of a hexagon with four adjacent triangles removed from the boundary
- Graphical condensation, overlapping Pfaffians and superpositions of matchings
- Lozenge tilings of hexagons with central holes and dents
- Chip removal. Urban renewal revisited
- Tiling enumeration of hexagons with off-central holes
- Replacing Pfaffians and applications
- A \(q\)-enumeration of lozenge tilings of a hexagon with three dents
- Perfect matchings on a type of lattices with toroidal boundary
- Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
- A quadratic identity for the number of perfect matchings of plane graphs
- Dimers belonging to three orientations on plane honeycomb lattices
- Graphical condensation for enumerating perfect matchings
- Pfaffian orientations and perfect matchings of scale-free networks
- Proof of a refinement of Blum's conjecture on hexagonal dungeons
- Maximum matchings in scale-free networks with identical degree distribution
This page was built for publication: Graphical condensation of plane graphs: a combinatorial approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817820)
