Graphical condensation of plane graphs: a combinatorial approach

DOI10.1016/J.TCS.2005.09.039MaRDI QIDQ817820zbMATH OpenOpenAlexFDO

Authors Weigen Yan, Yeong-Nan Yeh, Fuji Zhang

Publication date 20 March 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0509337

zbMATH Keywords

perfect matchingAztec diamondgraphical edge-condensationgraphical vertex-condensation

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

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

Cites work

• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A complementation theorem for perfect matchings of graphs having a cellular completion
• A simple proof of an identity concerning Pfaffians of skew symmetric matrices
• A simple proof of the Aztec diamond theorem
• Alternating-sign matrices and domino tilings. I
• Applications of graphical condensation for enumerating matchings and tilings
• Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers
• Enumeration of perfect matchings in graphs with reflective symmetry
• Generalized domino-shuffling.
• Graphical condensation for enumerating perfect matchings
• Overlapping Pfaffians
• Perfect matchings of cellular graphs
• Pfaffian forms and \(\Delta\)-matroids
• Pfaffian identities: A combinatorial approach

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
• Applications of graphical condensation for enumerating matchings and tilings
• Proof of a conjecture of Kenyon and Wilson on semicontiguous minors
• 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
• Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
• Perfect matchings on a type of lattices with toroidal boundary
• 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)