Menu
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 \emph{Ladder Graph} \(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}\).