2020/04/21 by Mollard, Michel
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2004.10198
The Fibonacci cube of dimension n, denoted as Γ n , is the subgraph of the n-cube 5 Q n induced by vertices with no consecutive 1's. 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 generalizations of Fibonacci cubes. The most direct generalization is the family Γ n (1 s) of subgraphs induced by strings without 1 s as a substring where s ≥ 2 is a given integer. In a precedent work 10 we proved the existence of a perfect code in Γ n (1 s) for n = 2 p -- 1 and s ≥ 3.2 p--2 for any integer p ≥ 2. The Lucas cube Λ n is obtained from Γ n by removing vertices that start and end with 1. Very often the same problems are studied on Fibonacci cubes and Lucas cube. In this note we prove the non-existence of perfect codes in Λ n for n ≥ 4 and 15 prove the existence of perfect codes in some generalized Lucas cube Λ n (1 s).