The existence of perfect codes in a family of generalized Fibonacci cubes

摘要

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. In an article of 2016 in this journal Ashrafi and his co-authors proved the non-existence of perfect codes in Gamma(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 Gamma(n)(1(s)) of subgraphs induced by strings without 1(s) as a substring where s = 2 is a given integer. We prove the existence of a perfect code in Gamma(n)(1(s)) for n = 2(p)-1 and s = 3.2(p-2) for any integer p = 2. (C) 2018 Elsevier B.V. All rights reserved.