The Number of Perfect Matchings in M\"obius Ladders and Prisms

arXiv2003.09602MaRDI QIDQ6337152FDOQ6337152

Publication date: 21 March 2020

Abstract: The 1970s conjecture of Lov'asz and Plummer that the number of perfect matchings in any

3

-regular graph is exponential in the number of vertices was proved in 2011 by Esperet, Kardov{s}, King, Kr'al', and Norine. We give the exact formula for the number of perfect matchings in two families of

3

-regular graphs. In the graph consisting of a

2 n

-cycle with diametric chords (also known as the M"obius ladder

M_{n}

and a Harary graph) and in the cartesian product of the cycle

C_{n}

with an edge (called the cycle prism), the number of matchings is the sum of the Fibonacci numbers

F_{n - 1}

and

F_{n + 1}

, plus two more for the M"obius ladder when

n

is odd and for the cycle prism when

n

is even.

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: The Number of Perfect Matchings in M\"obius Ladders and Prisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337152)