2014/02/25 by Jernej Azarija, Azarija, Jernej, Sandi Klavžar +7
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1402.6377
arxiv created 2014/02/25 · openalex publication_date 2014/02/25 · arxiv updated 2014/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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| ≥ (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 Qd(f) ≅ Qd(f') are characterized.