The (non-)existence of perfect codes in Lucas cubes

Author
Azam Ghaleh Agha Babai
University of Qom
Abstract
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
1. فتحعلیخانی خدیجه، خواص جبری و متریک ابرمکعب و برخی زیرگراف‌های آن، رساله دکتری، دانشگاه کاشان (1394).

2. فتحعلیخانی خدیجه، اشرفی علی‌رضا، خواص متریک و ترکیبیاتی مکعب‌های فیبوناتچی و لوکاس، مجله محاسبات نرم، سال پنجم، شماره اول، صص 101-78، (1395).

3. فتحعلیخانی خدیجه، اشرفی علی‌رضا، خواص جبری مکعب‌های فیبوناتچی و لوکاس، نشریه ریاضی و جامعه، جلد 2، شماره 2، صص 61-43، (1394).

4. Abay-Asmerom G., Hammack R. H., Taylor D. T., "Perfect r-codes in strong products of graphs", Bull. Inst. Combin. Appl., 55 (2009) 66–72.

5. Ashrafi A.R., Azarija J., Babai A., Fathalikhani Kh., Klavžar S.,"The (non-)existence of perfect codes in Fibonacci cubes", Information Processing Letters, 116 (2016) 387-390.

6. Biggs N., "Perfect codes in graphs", J. Comb. Theory, Ser. B 15 (1973) 289–296.

7. Dedó E., Torri D., Zagaglia Salvi N., "The observability of the Fibonacci and the Lucas cubes", Combinatorics ’98 (Palermo). Discrete Math., 255 (1-3) (2002) 55–63.

8. Gregor P., "Recursive fault-tolerance of Fibonacci cube in hypercubes", Discrete Math., 306 (13) (2006) 1327–1341.

9. Hsu W. J., "Fibonacci cubes- a new interconnection technology", IEEE Trans. Parallel Distrib. Syst., 4 (1) (1993) 3–12.

10. Klavžar S., "On median nature and enumerative properties of Fibonacci-like cubes", Discrete Math, 299 (1-3) (2005) 145–153.

11. Klavžar S., Mollard M., "Cube polynomial of Fibonacci and Lucas cubes", Acta Appl. Math, 117 (2012) 93–105.

12. Klavžar S., Peterin I., "Edge-counting vectors, Fibonacci cubes, and Fibonacci triangle", Publ. Math. Debrecen, 71 (3-4) (2007) 267–278.

13. Klavžar S., Špacapan S., Žerovnik J., "An almost complete description of perfect codes in direct products of cycles", Adv. in Appl. Math., 37 (1) (2006) 2–18.

14. Kratochvíl J., "Perfect codes over graphs", J. Comb. Theory, Ser. B, 40 (1986) 224–228.

15. Munarini E., Perelli Cippo C., Zagaglia Salvi N., "On the Lucas cubes", Fibonacci Quart., 39 (1) (2001) 12–21.

16. Zagaglia Salvi N., "The automorphism group of the Lucas semilattice", Bull. Inst. Combin. Appl., 34 (2002) 11–15.

17. Žerovnik J., "Perfect codes in direct products of cycles—a complete characterization", Adv. in Appl. Math. 41(2) (2008) 197–205.
Mathematical Research
Volume 8, Issue 3 - Serial Number 22
Autumn 2022
Pages 172-179