The (non-)existence of perfect codes in Lucas cubes - Mollard, Michel (Ars mathematica contemporanea, 2022)
The 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. 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 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 prove the existence of perfect codes in some generalized Lucas cube ?$Λ_n (1^s)$?.
Keywords: error correcting codes; Fibonacci cube; Fibonaccijeva kocka; kode za popravljanje napak; perfect code; popolna koda