Volume 8, Issue 3 (Vol. 8,No. 3, 2022)                   mmr 2022, 8(3): 172-179 | Back to browse issues page

BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Ghaleh Agha Babai A. The (non-)existence of perfect codes in Lucas cubes. mmr 2022; 8 (3) :172-179
URL: http://mmr.khu.ac.ir/article-1-3002-en.html
1- University of Qom , a_babai@aut.ac.ir
Abstract:   (466 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\$.