Jay Pantone

John Wesley Young Research Instructor
Dartmouth College


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.

Open Questions