On Disjoint hypercubes in Fibonacci cubes

Abstract

The {\em Fibonacci cube} of dimension $n$, denoted as $\Gamma \_n$, is the subgraph of $n$-cube $Q\_n$ induced by vertices with no consecutive 1's. We study the maximum number of disjoint subgraphs in $\Gamma \_n$ isomorphic to $Q\_k$, and denote this number by $q\_k(n)$. We prove several recursive results for $q\_k(n)$, in particular we prove that $q\_k(n)=q\_k-1(n-2)+q\_k(n-3)$. We also prove a closed formula in which $q\_k(n)$ is given in terms of Fibonacci numbers, and finally we give the generating function for the sequence $\{q\_k(n)\}\_{n=0}^{\infty }$.