2018/01/12 by Michel Mollard, Mollard, Michel
Computer Science · Engineering · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1801.04106
openalex publication_date 2018/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The \em Fibonacci cube of dimension n, denoted as Γ_n, is the subgraph of the n-cube Q_n induced by vertices with no consecutive 1's. In an article of 2016 Ashrafi and his co-authors proved the non-existence of perfect codes in Γ_n for n≥ 4. As an open problem the authors suggest to consider the existence of perfect codes in generalization of Fibonacci cubes. The most direct generalization is the family Γ_n(1s) of subgraphs induced by strings without 1s as a substring where s≥ 2 is a given integer. We prove the existence of a perfect code in Γ_n(1s) for n=2p-1 and s ≥ 3.2p-2 for any integer p≥ 2.