A new approach to solving three combinatorial enumeration problems on planar graphs

DOI10.1016/0166-218X(95)E0111-3zbMath0833.05043OpenAlexW1995138470MaRDI QIDQ1894355

Charles J. Colbourn, J. Scott Provan, Dirk Vertigan

Publication date: 11 March 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(95)e0111-3

zbMATH Keywords

algorithmplanar graphweightgraph transformationsnumber of spanning treesIsing partition functionnumber of perfect matchingsdelta-wye graph reduction

Mathematics Subject Classification ID

Trees (05C05) Applications of graph theory (05C90) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs ⋮ Untangling planar curves ⋮ Generalized domino-shuffling. ⋮ An algorithm for delta-wye reduction of almost-planar graphs ⋮ Counting spanning trees using modular decomposition ⋮ Counting Spanning Trees in Graphs Using Modular Decomposition ⋮ On spin models, triply regular association schemes, and duality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On two dual classes of planar graphs
• Matching theory
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Use of Wye-Delta Transformations in Network Simplification
• On the delta-wye reduction for planar graphs
• Generalized Nested Dissection
• The Recognition of Series Parallel Digraphs
• Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
• The Delta-Wye Approximation Procedure for Two-Terminal Reliability
• Beitrag zur Theorie des Ferromagnetismus
• Wye-Delta Transformation in Probablilistic Networks
• The Computational Complexity of Tutte Invariants for Planar Graphs