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

The Fibonacci cube Γₙ is the subgraph of the hypercube Qₙ induced by vertices with no consecutive 1s. We study a one parameter generalization, p-th order Fibonacci cubes Γ⁽ᵖ⁾ₙ, which are subgraphs of Qₙ induced by strings without p consecutive 1s. We show the link between vertices of Γ⁽ᵖ⁾ₙ and compositions of integers with parts in \1, 2, … , p\. Among other eumerative properties, we study the order, size and cube polynomial of Γ⁽ᵖ⁾ₙ 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 Γᵖₙ , 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.