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) is found. Strings f and f′ with |f|=|f′|=d−1 for which Qd(f)≅Qd(f′) are characterized.