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 |
| _version_ | 1797871675002322944 |
|---|---|
| author | Azam Ghaleh Agha Babai |
| author_facet | Azam Ghaleh Agha Babai |
| author_sort | Azam Ghaleh Agha Babai |
| collection | DOAJ |
| description | 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$. |
| first_indexed | 2024-04-10T00:46:28Z |
| format | Article |
| id | doaj.art-c132395e24b847689111883265a1f12b |
| institution | Directory Open Access Journal |
| issn | 2588-2546 2588-2554 |
| language | fas |
| last_indexed | 2024-04-10T00:46:28Z |
| publishDate | 2022-11-01 |
| publisher | Kharazmi University |
| record_format | Article |
| series | پژوهشهای ریاضی |
| spelling | doaj.art-c132395e24b847689111883265a1f12b2023-03-13T19:23:44ZfasKharazmi Universityپژوهشهای ریاضی2588-25462588-25542022-11-0183172179The (non-)existence of perfect codes in Lucas cubesAzam Ghaleh Agha Babai01 University of Qom 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$.http://mmr.khu.ac.ir/article-1-3002-en.htmlperfect codelucas cubefibonacci cube. |
| spellingShingle | Azam Ghaleh Agha Babai The (non-)existence of perfect codes in Lucas cubes پژوهشهای ریاضی perfect code lucas cube fibonacci cube. |
| title | The (non-)existence of perfect codes in Lucas cubes |
| title_full | The (non-)existence of perfect codes in Lucas cubes |
| title_fullStr | The (non-)existence of perfect codes in Lucas cubes |
| title_full_unstemmed | The (non-)existence of perfect codes in Lucas cubes |
| title_short | The (non-)existence of perfect codes in Lucas cubes |
| title_sort | non existence of perfect codes in lucas cubes |
| topic | perfect code lucas cube fibonacci cube. |
| url | http://mmr.khu.ac.ir/article-1-3002-en.html |
| work_keys_str_mv | AT azamghalehaghababai thenonexistenceofperfectcodesinlucascubes AT azamghalehaghababai nonexistenceofperfectcodesinlucascubes |