Graphical condensation of plane graphs: a combinatorial approach

DOI10.1016/j.tcs.2005.09.039zbMath1086.05066arXivmath/0509337OpenAlexW1974219541MaRDI QIDQ817820

Weigen Yan, Yeong-Nan Yeh, Fu Ji 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)

Related Items (14)

Tiling enumeration of hexagons with off-central holes ⋮ A \(q\)-enumeration of lozenge tilings of a hexagon with four adjacent triangles removed from the boundary ⋮ Proof of a conjecture of Kenyon and Wilson on semicontiguous minors ⋮ A quadratic identity for the number of perfect matchings of plane graphs ⋮ 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 new expression for matching polynomials ⋮ Dimers belonging to three orientations on plane honeycomb lattices ⋮ Proof of a refinement of Blum's conjecture on hexagonal dungeons ⋮ Maximum matchings in scale-free networks with identical degree distribution ⋮ Pfaffian orientations and perfect matchings of scale-free networks ⋮ Lozenge tilings of hexagons with central holes and dents

Cites Work

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

This page was built for publication: Graphical condensation of plane graphs: a combinatorial approach