The (non-)existence of perfect codes in Lucas cubes
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 =...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | fas |
| Published: |
Kharazmi University
2022-11-01
|
| Series: | پژوهشهای ریاضی |
| Subjects: | |
| Online Access: | http://mmr.khu.ac.ir/article-1-3002-en.html |
| Summary: | 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$. |
|---|---|
| ISSN: | 2588-2546 2588-2554 |