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.

- Journal: European Journal of Combinatorics
- arXiv: 1402.6377 [math.CO]

**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')\).