Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652617 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
Lovász and Plummer conjectured, in the mid 1970ʼs, that every bridgeless cubic graph has exponentially many perfect matchings. In this work we show that every cubic planar graph G whose geometric dual graph is a stack triangulation (planar 3-tree) has at least 3ϕ|V(G)|/72 distinct perfect matchings, where ϕ is the golden ratio. Our work builds on a novel approach relating Lovász and Plummerʼs claim and the number of so called groundstates of the widely studied Ising model.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics