2010/10/28 by Jiménez, Andrea, Kiwi, Marcos
#05C30 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1010.5918
Lovász and Plummer conjectured, in the mid 1970's, that every cubic graph G with no cutedge has an exponential in |V(G)| number of perfect matchings. In this work we show that every cubic planar graph G whose geometric dual graph is a stack triangulation has at least 3 times the golden ratio to |V(G)|/72 distinct perfect matchings. Our work builds on a novel approach relating Lovász and Plummer's conjecture and the number of so called groundstates of the widely studied Ising model from statistical physics.