ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P3.10 / 519–525 https://doi.org/10.26493/1855-3974.2308.de6 (Also available at http://amc-journal.eu) The (non-)existence of perfect codes in Lucas cubes* Michel Mollard Institut Fourier, CNRS, Université Grenoble Alpes, France Received 10 April 2020, accepted 10 December 2021, published online 9 June 2022 Abstract The Fibonacci cube of dimension n, denoted as Γn, is the subgraph of the n-cube Qn induced by vertices with no consecutive 1’s. Ashrafi and his co-authors proved the non- existence of perfect codes in Γn for n ≥ 4. As an open problem the authors suggest to consider the existence of perfect codes in generalizations of Fibonacci cubes. The most direct generalization is the family Γn(1s) of subgraphs induced by strings without 1s as a substring where s ≥ 2 is a given integer. In a precedent work we proved the existence of a perfect code in Γn(1s) for n = 2p − 1 and s ≥ 3.2p−2 for any integer p ≥ 2. The Lucas cube Λn is obtained from Γn by removing vertices that start and end with 1. Very often the same problems are studied on Fibonacci cubes and Lucas cube. In this note we prove the non-existence of perfect codes in Λn for n ≥ 4 and prove the existence of perfect codes in some generalized Lucas cube Λn(1s). Keywords: Error correcting codes, perfect code, Fibonacci cube. Math. Subj. Class. (2020): 94B50, 05C69 1 Introduction and notations An interconnection topology can be represented by a graph G = (V,E), where V denotes the processors and E the communication links. The hypercube Qn is a popular intercon- nection network because of its structural properties. The Fibonacci cube was introduced in [8] as a new interconnection network. This graph is an isometric subgraph of the hypercube which is inspired in the Fibonacci numbers. It has attractive recurrent structures such as its decomposition into two subgraphs which are also Fibonacci cubes by themselves. Structural properties of these graphs were more extensively studied afterwards. See [12] for a survey. *Footnote on the title. E-mail address: michel.mollard@univ-grenoble-alpes.fr (Michel Mollard) cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 520 Ars Math. Contemp. 22 (2022) #P3.10 / 519–525 Lucas cubes, introduced in [17], have attracted the attention as well due to the fact that these cubes are closely related to the Fibonacci cubes. They have also been widely studied [3, 4, 6, 11, 13, 14, 18, 20, 23]. We will next define some concepts needed in this paper. Let G be a connected graph. The open neighbourhood of a vertex u is NG(u) the set of vertices adjacent to u. The closed neighbourhood of u is NG[u] = NG(u) ∪ {u}. The distance between two vertices denoted dG(x, y) is the length of a shortest path between x and y. We have thus NG[u] = {v ∈ V (G); dG(u, v) ≤ 1}. We will use the notations d(x, y) and N [u] when the graph is unambiguous. A dominating set D of G is a set of vertices such that every vertex of G belongs to the closed neighbourhood of at least one vertex of D. In [2], Biggs initiated the study of perfect codes in graphs as a generalization of classical 1-error perfect correcting codes. A code C in G is a set of vertices C such that for every pair of distinct vertices c, c′ of C we have NG[c] ∩NG[c′] = ∅ or equivalently such that dG(c, c′) ≥ 3. A perfect code of a graph G is both a dominating set and a code. It is thus a set of vertices C such that every vertex of G belongs to the closed neighbourhood of exactly one vertex of C. A perfect code is also known as an efficient dominating set. The existence or non-existence of perfect codes have been considered for many graphs. See the introduction of [1] for some references. The vertex set of the n-cube Qn is the set Bn of binary strings of length n, two vertices being adjacent if they differ in precisely one position. Classical 1-error correcting codes and perfect codes are codes and perfect codes in the graph Qn. The weight of a binary string is the number of 1s. The concatenation of strings x and y is denoted x||y or just xy when there is no ambiguity. A string f is a substring of a string s if there exist strings x and y, may be empty, such that s = xfy. A Fibonacci string of length n is a binary string b = b1 . . . bn with bi · bi+1 = 0 for 1 ≤ i < n. In other words a Fibonacci string is a binary string without 11 as substring. The Fibonacci cube Γn (n ≥ 1) is the subgraph of Qn induced by the Fibonacci strings of length n. Adjacent vertices in Γn differ in one bit. Because of the empty string, Γ0 = K1. A Fibonacci string of length n is a Lucas string if b1 · bn ̸= 1. That is, a Lucas string has no two consecutive 1’s including the first and the last elements of the string. The Lucas cube Λn is the subgraph of Qn induced by the Lucas strings of length n. We have Λ0 = Λ1 = K1. Let Fn and Ln be the set of strings of Fibonacci strings and Lucas strings of length n. By Γn,k and Λn,k we denote the vertices of of weight k in respectively Γn and Λn. Since Ln = {0s; s ∈ Fn−1} ∪ {10s0; s ∈ Fn−3} and |Γn,k| = ( n− k + 1 k ) it is immediate to derive the following classical result. Proposition 1.1. Let n ≥ 1. The number of vertices of weight k ≤ n in Λn is |Λn,k| = ( n− k k ) + ( n− k − 1 k − 1 ) . M. Mollard: The (non-)existence of perfect codes in Lucas cubes 521 u u u 01 00 10 u u u u 001 000 010 100 u u u u u u u 0001 0000 0010 01001000 1010 0101 u u u u u u u uu u u 00001 00000 00010 00100 01001 10000 01000 01010 00101 10100 10010 Figure 1: Γ2 = Λ2, Λ3, Λ4 and Λ5. It will be convenient to consider the binary strings of length n as vectors of Fn the vector space of dimension n over the field F = Z2 thus to associate to a string x1x2 . . . xn the vector θ(x1x2 . . . xn) = (x1, x2, . . . , xn). The Hamming distance between two vectors x,y ∈ Fn, d(x,y) is the number of coordinates in which they differ. By the correspon- dence θ we can define the binary sum x+ y and the Hamming distance d(x,y) of strings in Bn. Note that the Hamming distance is the usual graph distance in Qn. We will first recall some basic results about perfect codes in Qn. Since Qn is a regular graph of degree n the existence of a perfect code of cardinality |C| implies |C|(n+1) = 2n thus a necessary condition of existence is that n + 1 is a power of 2 thus that n = 2p − 1 for some integer p. For any integer p Hamming [7] constructed, a linear subspace of F2p−1 which is a perfect code. It is easy to prove that all linear perfect codes are Hamming codes. Notice that 1n belongs to the Hamming code of length n. In 1961 Vasilev [22], and later many authors, see [5, 21] for a survey, constructed perfect codes which are not linear codes. In a recent work [1] Ashrafi and his co-authors proved the non-existence of perfect codes in Γn for n ≥ 4. As an open problem the authors suggest to consider the existence of perfect codes in generalizations of Fibonacci cubes. The most complete generalization proposed in [9] is, for a given string f , to consider Γn(f) the subgraph of Qn induced by strings that do not contain f as substring. Since Fibonacci cubes are Γn(11) the most immediate generalization [15, 19] is to consider Γn(1s) for a given integer s. In [16] we proved the existence of a perfect code in Γn(1s) for n = 2p − 1 and s ≥ 3.2p−2 for any integer p ≥ 2. In the next section we will prove the main result of this note. Theorem 1.2. The Lucas cube Λn, n ≥ 0, admits a perfect code if and only if n ≤ 3 . 2 Perfect codes in Lucas cube It can be easily checked by hand that {0n} is a perfect code of Λn for n ≤ 3 and that Λ4 and Λ5 do not contain a perfect code (Figure 1). Assume thus n ≥ 6. Note first that from Proposition 1.1 we have |Λn,2| = n(n− 3) 2 and |Λn,3| = n(n− 4)(n− 5) 6 . Therefore Λn,2 and Λn,3 are none empty. 522 Ars Math. Contemp. 22 (2022) #P3.10 / 519–525 Let Λ1n,k be the vertices of Λn,k that start with 1. Since Ln = {0s; s ∈ Fn−1} ∪ {10s0; s ∈ Fn−3} the number of vertices in Λ1n,k is |Λ1n,k| = |Γn−3,k−1| = ( n− 1− k k − 1 ) . Lemma 2.1. If n ≥ 6 and C is a perfect code of Λn then 0n ∈ C. Proof. Suppose on the contrary that 0n /∈ C. Since 0n must be dominated there exists a vertex in Λn,1 ∩ C. This vertex is unique and because of the circular symmetry of Λn we can assume 10n−1 ∈ C. Since 0n /∈ C the other vertices of Λn,1 must be dominated by vertices in Λn,2. But a vertex in Λn,2 has precisely two neighbors in Λn,1 thus n must be odd and |Λn,2 ∩ C| = n− 1 2 . The unique vertex 10n−1 in Λn,1∩C has exactly n−3 neighbors in Λn,2. Let D be the vertices of Λn,2 not in C and not dominated by 10n−1. Vertices in D must be dominated by vertices in Λn,3 ∩ C. Each vertex of Λn,3 ∩ C has exactly exacty three neighbors in Λn,2. Thus 3 divides the number of vertices in D. This number is |D| = |Λn,2| − (n− 3)− n− 1 2 = n2 − 6n+ 7 2 . This is not possible since there exists no odd integer n such that 6 divides n2 + 1. Indeed since n is odd, 6 does not divide n thus divides (n+1)(n−1) = n2−1 or (n+2)(n−2) = n2 − 4 or (n+ 3)(n− 3) = n2 − 9 thus cannot divide n2 + 1. We are now going to prove Theorem 1.2. Proof of Theorem 1.2. Let n ≥ 6 and C be a perfect code. Since 0n ∈ C all vertices of Λn,1 are dominated by 0n and thus Λn,2 ∩ C = Λn,1 ∩ C = ∅. Consequently, each vertex of Λn,2 must be dominated by a vertex in Λn,3. Since each vertex in Λn,3 has precisely three neighbors in Λn,2 we obtain that |Λn,3 ∩ C| = |Λn,2| 3 . This number must be an integer thus 3 divides |Λn,2| = n(n−3)2 and therefore 3 divides n(n− 3). This is only possible if n is a multiple of 3. Each vertex of Λ1n,2 must be dominated by a vertex in Λ 1 n,3. Furthermore a vertex in Λ1n,3 has precisely two neighbors in Λ 1 n,2. Therefore |Λ1n,2| = n− 3 must be even and thus n = 6p+ 3 for some integer p ≥ 1. Let E be the set of vertices of Λn,3 not in C. Vertices in E must be dominated by a vertex in Λn,4. Furthermore each vertex in Λn,4 has precisely four neighbors in Λn,3. Therefore 4 divides |E| with |E| = |Λn,3| − |Λn,3 ∩ C| = n(n− 4)(n− 5) 6 − n(n− 3) 6 = n(n2 − 10n+ 23) 6 . Replacing n by 6p+3 we obtain that 4 divides the odd number (2p+1)(18p2 − 12p+1). This contradiction proves Theorem 1.2. M. Mollard: The (non-)existence of perfect codes in Lucas cubes 523 3 Perfect codes in generalized Lucas cube The analogous of the generalisation of Fibonacci cube Γn(1s) for Lucas cube is the family Λn(1 s) of subgraphs of Qn induced by strings without 1s as a substring in a circular man- ner where s ≥ 2 is a given integer. More formally [10] for any binary strings b1b2 . . . bn and each 1 ≤ i ≤ n, call bibi+1 . . . bnb1 . . . bi−1 the i-th circulation of b1b2 . . . bn. The gener- alized Lucas cube Λn(1s) is the subgraph of Qn induced by strings without a circulation containing 1s as a substring. In [16] the existence of a perfect code in Γn(1s) is proved for n = 2p−1 and s ≥ 3.2p−2 for any integer p ≥ 2. The strategy used in this construction is to build a perfect code C in Qn such that no vertex of C contains 1s as substring. The set C is also a perfect code in Γn(1s) since each vertex of Γn(1s) belongs to the unique closed neighbourhood in Qn thus in Γn(1s) of a vertex in C. Because of the following proposition we cannot use the same idea for Λn(1s) and s ≤ n− 1. Proposition 3.1. Let n be an integer and 2 ≤ s ≤ n− 1. If C is a perfect code in Qn then some word of C contains a circulation of 1s as a substring. Proof. Let C be a such a perfect code in Qn then 1n /∈ C. Thus 1n must be neighbour of a vertex c in C. Since c = 1i01n−1−i for some integer i the i+ 1th-circulation of c is 1n−10. We can supplement this proposition by the two following results. Proposition 3.2. Let p ≥ 2 and n = 2p − 1 then there exists a perfect code in Λn(1n) of order |C| = 2 n n+1 . Proof. Let D be a Hamming code of length n and C = {d + (0n−11); d ∈ D}. Since 1n ∈ D, the set C is a perfect code of Qn such that 1n /∈ C. Since Λn(1n) is obtained from Qn by the deletion of 1n every vertex of Λn(1n) is in the closed neighbourhood of exactly one vertex of C. Proposition 3.3. Let p ≥ 2 and n = 2p − 1 then there exists a perfect code in Λn(1n−1) and in Λn(1n−2) of order |C| = 2 n n+1 − 1. Proof. Let D be a Hamming code of length n. Then D is a perfect code of Qn such that 1n ∈ D. Since Λn(1n−1) is obtained from Qn by the deletion of the closed neighbourhood of 1n every vertex of Λn(1n−1) is in the closed neighbourhood of exactly one vertex of C = D − {1n}. Furthermore since 1n ∈ D there is no vertex of weight n− 2 in D. Let u be a vertex of Λn(1n−2) and f(u) be the vertex in D such that u ∈ NQn [u]. Since there is no vertex in D with weight n− 1 or n− 2 there is no circulation of f(u) containing 1n−2 as a substring. Therefore f(u) is a vertex of Λn(1n−2) and u ∈ NΛn(1n−2)[f(u)]. Since a code in Qn is a code in each of its subgraph C is a perfect code of Λn(1n−2). ORCID iDs Michel Mollard https://orcid.org/0000-0002-3602-8019 524 Ars Math. Contemp. 22 (2022) #P3.10 / 519–525 References [1] A. R. Ashrafi, J. Azarija, A. Babai, K. Fathalikhani and S. Klavžar, The (non-) existence of perfect codes in Fibonacci cubes, Inf. Process. Lett. 116 (2016), 387–390, doi:10.1016/j.ipl. 2016.01.010. [2] N. Biggs, Perfect codes in graphs, J. Comb. Theory, Ser. B 15 (1973), 289–296, doi:10.1016/ 0095-8956(73)90042-7. [3] A. Castro, S. Klavžar, M. Mollard and Y. Rho, On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes, Comput. Math. Appl. 61 (2011), 2655–2660, doi:10.1016/j.camwa.2011.03.012. [4] A. Castro and M. Mollard, The eccentricity sequences of Fibonacci and Lucas cubes, Discrete Math. 312 (2012), 1025–1037, doi:10.1016/j.disc.2011.11.006. [5] G. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering Codes, volume 54 of North-Holland Math. Libr., Elsevier, Amsterdam, 1997, doi:10.1016/s0924-6509(97)x8001-8. [6] E. Dedó, D. Torri and N. Zagaglia Salvi, The observability of the Fibonacci and the Lucas cubes, Discrete Math. 255 (2002), 55–63, doi:10.1016/s0012-365x(01)00387-9. [7] R. W. Hamming, Error detecting and error correcting codes, Bell Syst. Tech. J. 29 (1950), 147– 160, doi:10.1002/j.1538-7305.1950.tb00463.x. [8] W.-J. Hsu, Fibonacci cubes-a new interconnection topology, IEEE Transactions on Parallel and Distributed Systems 4 (1993), 3–12, doi:10.1109/71.205649. [9] A. Ilić, S. Klavžar and Y. Rho, Generalized Fibonacci cubes, Discrete Math. 312 (2012), 2–11, doi:10.1016/j.disc.2011.02.015. [10] A. Ilić, S. Klavžar and Y. Rho, Generalized Lucas cubes, Appl. Anal. Discrete Math. 6 (2012), 82–94, doi:10.2298/aadm120108002i. [11] A. Ilić and M. Milošević, The parameters of Fibonacci and Lucas cubes, Ars Math. Contemp. 12 (2017), 25–29, doi:10.26493/1855-3974.915.f48. [12] S. Klavžar, Structure of Fibonacci cubes: a survey, J. Comb. Optim. 25 (2013), 505–522, doi: 10.1007/s10878-011-9433-z. [13] S. Klavžar and M. Mollard, Cube polynomial of Fibonacci and Lucas cubes, Acta Appl. Math. 117 (2012), 93–105, doi:10.1007/s10440-011-9652-4. [14] S. Klavžar, M. Mollard and M. Petkovšek, The degree sequence of Fibonacci and Lucas cubes, Discrete Math. 311 (2011), 1310–1322, doi:10.1016/j.disc.2011.03.019. [15] J. Liu and W.-J. Hsu, Distributed algorithms for shortest-path, deadlock-free routing and broad- casting in a class of interconnection topologies, in: Proceedings Sixth International Parallel Processing Symposium, 1992 pp. 589–596, doi:10.1109/ipps.1992.222963. [16] M. Mollard, The existence of perfect codes in a family of generalized Fibonacci cubes, Inf. Process. Lett. 140 (2018), 1–3, doi:10.1016/j.ipl.2018.07.010. [17] E. Munarini, C. Perelli Cippo and N. Salvi, On the Lucas cubes, Fibonacci Q. 39 (2001), https://www.fq.math.ca/39-1.html. [18] M. Ramras, Congestion-free routing of linear permutations on Fibonacci and Lucas cubes, Australas. J. Comb. 60 (2014), 1–10, https://ajc.maths.uq.edu.au/?page=get_ volumes&volume=60. [19] N. Z. Salvi, On the existence of cycles of every even length on generalized Fibonacci cubes, Matematiche 51 (1996), 241–251, https://lematematiche.dmi.unict.it/ index.php/lematematiche/article/view/475. M. Mollard: The (non-)existence of perfect codes in Lucas cubes 525 [20] E. Saygi and Ö. Eğecioğlu, q-counting hypercubes in Lucas cubes, Turk. J. Math. 42 (2018), 190–203, doi:10.3906/mat-1605-2. [21] F. I. Solov’eva, On perfect binary codes, in: General theory of information transfer and com- binatorics, Elsevier, Amsterdam, pp. 371–372, 2005, doi:10.1016/j.endm.2005.07.059. [22] Y. Vasil’ev, On nongroup close-packed codes, Probl. Kibern. 8 (1962), 337–339. [23] X. Wang, X. Zhao and H. Yao, Structure and enumeration results of matchable Lucas cubes, Discrete Appl. Math. 277 (2020), 263–279, doi:10.1016/j.dam.2019.09.011.