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. An example of a family of such strings f, f ′, where |f | = |f ′ | ≥ 23 (d + 1) are found. Strings f and f ′ with |f | = |f ′ | = d − 1 for which Qd(f) ∼ = Qd(f ′) are characterized