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

XML Persian Abstract Print


Download citation:
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:   (385 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$.
Full-Text [PDF 1030 kb]   (112 Downloads)    
Type of Study: Original Manuscript | Subject: alg
Received: 2019/09/30 | Revised: 2023/06/17 | Accepted: 2020/11/23 | Published: 2022/12/20 | ePublished: 2022/12/20

Add your comments about this article : Your username or Email:
CAPTCHA

Send email to the article author


Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2024 CC BY-NC 4.0 | Mathematical Researches

Designed & Developed by : Yektaweb