Maximal hypercubes in Fibonacci and Lucas cubes

Abstract

The Fibonacci cube ${\Gamma }_n$ is the subgraph of the hypercube induced by the binary strings that contain no two consecutive 1's. The Lucas cube ${\Lambda }_n$ is obtained from ${\Gamma }_n$ by removing vertices that start and end with 1. We characterize maximal induced hypercubes in ${\Gamma }_n$ and ${\Lambda }_n$ and deduce for any $p\le n$ the number of maximal $p$-dimensional hypercubes in these graphs.