Connected cubic graphs with the maximum number of perfect matchings

Abstract

It is proved that for $n\ge 6$, the number of perfect matchings in a simple connected cubic graph on $2n$ vertices is at most $4f_{n-1}$, with $f_n$ being the $n$-th Fibonacci number. The unique extremal graph is characterized as well. In addition, it is shown that the number of perfect matchings in any cubic graph $G$ equals the expected value of a random variable defined on all $2$-colorings of edges of $G$. Finally, an improved lower bound on the maximum number of cycles in a cubic graph is provided.

22 pages, 20 figures; final version

References in corpus (1)

• Exponentially many perfect matchings in cubic graphs

Cited by in corpus (1)

• Nice vertices in cubic graphs