Enumerating Perfect Matchings in Inductively-Defined Families of Graphs

Abstract

In this paper, we look at families $\{G_n\}$ of graphs (for $n>0$) for which the number of perfect matchings of $G_n$ is the $n$th term in a sequence of generalized Fibonacci numbers. A one-factor of a graph is a set of edges forming a spanning one-regular subgraph (a perfect matching). The generalized Fibonacci numbers are the integers produced by a two-term homogeneous linear recurrence from given initial values. We explore the construction of such families of graphs, using as our motivation the $LadderGraph$ $L_n$; it is well-known that $L_n$ has exactly $F_{n+1}$ perfect matchings, where $F_n$ is the traditional Fibonacci sequence, defined by $F_1=F_2=1$, and $F_{n+1}=F_n+F_{n-1}$.