On Isomorphism Classes of Generalized Fibonacci Cubes

The generalized Fibonacci cube Qd(f) is the subgraph of the d-cube Qd induced on the set of all strings of length d that do not contain f as a substring. It is proved that if Qd(f) ∼ = Qd(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 Qd(f) ∼ = Qd(f ′), where |f| ≥ 23 (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 Qd(f) ∼ = Qd(f′) are characterized