Jay Pantone

On Isomorphism Classes of Generalized Fibonacci Cubes

with Jernej Azarija, Sandi Klavžar, Jaehun Lee, and Yoomi Rho

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')$$ then $$|f|=|f'|$$. 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'$$ such that $$Q_d(f) \cong Q_d(f')$$, where $$|f| \ge \frac{2}{3}(d+1)$$ and $$f'$$ cannot be obtained from $$f$$ by its reversal or binary complementation. Strings $$f$$ and $$f'$$ with $$|f|=|f'|=d-1$$ for which $$Q_d(f) \cong Q_d(f')$$ are characterized.

• Conjecture 2.4: If $$f$$ and $$f'$$ are binary strings such that $$Q_d(f) \cong Q_d(f')$$, then $$Q_{d-1}(f) \cong Q_{d-1}(f')$$.
• Conjecture 2.5: Let $$f, f'$$ be a non-trivial pair such that $$Q_d(f) \cong Q_d(f')$$. Then $$|f| \geq \frac{2}{3}(d+1)$$.
• Conjecture 3.2: Let $$f, f'$$ be a non-trivial pair such that $$Q_d(f) \cong Q_d(f')$$. Then $$\nu(f) = \nu(f')$$.