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

english

2022

volume 22, issue 3

error correcting codes   Fibonacci cube   perfect code

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

The Fibonacci cube of dimension ?$n$?, denoted as ?$\Gamma_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 ?$\Gamma_n$? for ?$n \geq 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 ?$\Gamma_n (1^s)$? of subgraphs induced by strings without ?$1^s$? as a substring where ?$s \geq 2$? is a given integer. In a precedent work we proved the existence of a perfect code in ?$\Gamma_n (1^s)$? for ?$n = 2^p - 1$? and ?$s \geq 3.2^{p-2}$? for any integer ?$p \geq 2$?. The Lucas cube ?$\Lambda_n$? is obtained from ?$\Gamma_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 ?$\Lambda_n$? for ?$n \geq 4$? and prove the existence of perfect codes in some generalized Lucas cube ?$\Lambda_n (1^s)$?.

22.11.2022