Abstract
The 1970s conjecture of Lovász and Plummer that the number of perfect matchings in any -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 -regular graphs. In the graph consisting of a -cycle with diametric chords (also known as the Möbius ladder and a Harary graph) and in the cartesian product of the cycle with an edge (called the cycle prism), the number of matchings is the sum of the Fibonacci numbers and , plus two more for the Möbius ladder when is odd and for the cycle prism when is even.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.