The (non-)existence of perfect codes in Lucas cubes

Michel Mollard


The Fibonacci cube of dimension n, denoted as Γn, is the subgraph of the n-cube Qn 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(1s) of subgraphs induced by strings without 1s as a substring where s ≥ 2 is a given integer. In a precedent work we proved the existence of a perfect code in Γn(1s) for n = 2p − 1 and s ≥ 3.2p − 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 prove the existence of perfect codes in some generalized Lucas cube Λn(1s).


Error correcting codes, perfect code, Fibonacci cube

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications