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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.endm.2011.05.039 | Electronic Notes in Discrete Mathematics |
Keywords | DocType | Volume |
ising model,cubic graph,golden ratio,planar graph | Journal | 37 |
ISSN | Citations | PageRank |
1571-0653 | 2 | 0.40 |
References | Authors | |
2 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrea Jiménez | 1 | 8 | 4.13 |
Marcos A. Kiwi | 2 | 169 | 24.15 |