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

• Fibonacci cubes are isometric subgraphs of hypercubes and form an appealing model for interconnection networks.
• The study of codes in graphs presents a wide generalization of the problem of the existence of classical error-correcting codes.
• In this paper, it is proved that Fibonacci cubes do not admit any perfect code, unless the dimension is less than or equal to 3.

The Fibonacci cube ΓnΓn is obtained from the n  -cube QnQn by removing all the vertices that contain two consecutive 1s. It is proved that ΓnΓn admits a perfect code if and only if n≤3n≤3.