On Isomorphism Classes of Generalized Fibonacci Cubes

Abstract

The generalized Fibonacci cube $Q_d(f)$ is the subgraph of the $d$-cube $Q_d$ induced on the set of all strings of length $d$ that do not contain $f$ as a substring. It is proved that if $Q_d(f)\cong Q_d(f^{\prime })$ then $|f|=|f^{\prime }|$. The key tool to prove this result is a result of Guibas and Odlyzko about the autocorrelation polynomial associated to a binary string. It is also proved that there exist pairs of strings $f,f^{\prime }$ such that $Q_d(f)\cong Q_d(f^{\prime })$, where $|f|\ge \frac{2}{3}(d+1)$ and $f^{\prime }$ cannot be obtained from $f$ by its reversal or binary complementation. Strings $f$ and $f^{\prime }$ with $|f|=|f^{\prime }|=d-1$ for which $Q_d(f)\cong Q_d(f^{\prime })$ are characterized.