$p$-th order generalized Fibonacci cubes and maximal cubes in Fibonacci $p$-cubes

Abstract

The Fibonacci cube ${\Gamma }_n$ is the subgraph of the hypercube $Q_n$ induced by vertices with no consecutive 1s. We study a one parameter generalization, p-th order Fibonacci cubes ${\Gamma }_n^{(p)}$, which are subgraphs of $Q_n$ induced by strings without p consecutive 1s. We show the link between vertices of ${\Gamma }_n^{(p)}$ and compositions of integers with parts in $\{1,2,\dots ,p\}$. Among other eumerative properties, we study the order, size and cube polynomial of ${\Gamma }_n^{(p)}$ as well as their generating functions. Many of the given expressions are similar to those for Fibonacci cubes, where the $p$-nomial coefficients play the role of binomial coefficients. We also show that maximal induced hypercubes in Fibonacci $p$-cubes ${\Gamma }_n^p$ , another generalization of Fibonacci cubes, are connected to vertices of $(p+1)$-th order Fibonacci cubes. We use this link to determine the maximal cube polynomial of Fibonacci $p$-cubes.

IF-PREPUB