Counting perfect matchings of cubic graphs in the geometric dual

Details Counting perfect matchings of cubic graphs in the geometric dual Counting perfect matchings of cubic graphs in the geometric dual

2010-10-28

arxiv.org/abs/1010.5918v1

Mathematics

Combinatorics

18 pages, 8 figures

Scientific paper

Lov\'asz 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\'asz and Plummer's conjecture and the number of so called groundstates of the widely studied Ising model from statistical physics.

Affiliated with

Also associated with

No associations

Rating

Counting perfect matchings of cubic graphs in the geometric dual does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting perfect matchings of cubic graphs in the geometric dual, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting perfect matchings of cubic graphs in the geometric dual will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583716