The Number of Perfect Matchings in Möbius Ladders and Prisms

preprint2020arXivOpen access

Abstract

The 1970s conjecture of Lovász and Plummer that the number of perfect matchings in any 33-regular graph is exponential in the number of vertices was proved in 2011 by Esperet, Kardoš, King, Král', and Norine. We give the exact formula for the number of perfect matchings in two families of 33-regular graphs. In the graph consisting of a 2n2n-cycle with diametric chords (also known as the Möbius ladder MnM_n and a Harary graph) and in the cartesian product of the cycle CnC_n with an edge (called the cycle prism), the number of matchings is the sum of the Fibonacci numbers Fn−1F_{n-1} and Fn+1F_{n+1}, plus two more for the Möbius ladder when nn is odd and for the cycle prism when nn is even.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.