[Home ] [Archive]   [ فارسی ]
 Search Submit Contact
 Volume 8, Issue 3 (Vol. 8,No. 3, 2022)
 2022, 8(3): 172-179 Back to browse issues page
The (non-)existence of perfect codes in Lucas cubes
Azam Ghaleh Agha Babai1
1- University of Qom , a_babai@aut.ac.ir
Abstract:   (97 Views)
A Fibonacci string of length \$n\$ is a binary string \$b = b_1b_2ldots b_n\$ in which for every \$1 leq i < n\$, \$b_icdot b_{i+1} = 0\$. In other words, a Fibonacci string is a binary string without 11 as a substring.
Similarly, a Lucas string is a Fibonacci string \$b_1b_2ldots b_n\$ that \$b_1cdot b_n = 0\$.
For a natural number \$ngeq1\$, a Fibonacci cube of dimension \$n\$ is denoted by \$Gamma_n\$ and is defined as a graph whose vertices are  Fibonacci strings of length \$n\$ such that two vertices \$b_1b_2ldots b_n\$ and \$b'_1b'_2ldots b'_n\$ are adjacent if \$b_ineq b'_i\$ holds for exactly one \$iin{1,ldots, n}\$.
A Lucas cube of  dimension \$n\$, \$Lambda_n\$, is a subgraph of \$Gamma_n\$ induced by the Lucas strings of length \$n\$.

Let \$G=(V,E)\$ be a simple undirected graph. A perfect code is a subset \$C\$ of \$V\$ in such a way that for every \$vin C\$, the sets \${uin V | d(u, v) = 1}\$ are pairwise disjoint and make a partition for \$V\$. In other words, each vertex of \$G\$ is either in \$C\$ or is adjacent to exactly one of the elements of \$C\$. It is proved that Fibonacci cube \$Gamma_n\$, admits a perfect code if and only if \$nleq3\$.

In this paper, we prove the same result for Lucas cubes i.e, \$Lambda_n\$ admits a perfect code if and only if \$nleq3\$.
Keywords: Perfect code, Lucas cube, Fibonacci cube.
Type of Study: Original Manuscript | Subject: alg
Received: 2019/09/30 | Revised: 2023/01/1 | Accepted: 2020/11/23 | Published: 2022/12/20 | ePublished: 2022/12/20
Send email to the article author