318 KB17 KB200820252022Mollard, Michelletnik:22številka:3P3.10 (7 str.)DOI:10.26493/1855-3974.2308.de6COBISSID_HOST:118549507ISSN:1855-3966URN:URN:NBN:SI:doc-I3WC4A8LenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaerror correcting codesFibonacci cubeFibonaccijeva kockakode za popravljanje napakperfect codepopolna kodaThe (non-)existence of perfect codes in Lucas cubes|The Fibonacci cube of dimension ?$n$?, denoted as ?$\Gamma_n$?, is the subgraph of the ?$n$?-cube ?$Q_n$? induced by vertices with no consecutive 1's. Ashrafi and his co-authors proved the non-existence of perfect codes in ?$\Gamma_n$? for ?$n \geq 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 ?$\Gamma_n (1^s)$? of subgraphs induced by strings without ?$1^s$? as a substring where ?$s \geq 2$? is a given integer. In a precedent work we proved the existence of a perfect code in ?$\Gamma_n (1^s)$? for ?$n = 2^p - 1$? and ?$s \geq 3.2^{p-2}$? for any integer ?$p \geq 2$?. The Lucas cube ?$\Lambda_n$? is obtained from ?$\Gamma_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 ?$\Lambda_n$? for ?$n \geq 4$? and prove the existence of perfect codes in some generalized Lucas cube ?$\Lambda_n (1^s)$?Fibonaccijeva kocka dimenzije ?$n$?, označena z ?$\Gamma_n$?, je podgraf ?$n$?-kocke ?$Q_n$?, ki je induciran z vozlišči brez zaporednih 1. Ashrafi in njegovi soavtorji so dokazali neobstoj popolnih kod v ?$\Gamma_n$? za ?$n \geq 4$?. Kot odprt problem predlagajo obravnavo obstoja popolnih kod v posplošitvah Fibonaccijevih kock. Najbolj neposredna posplošitev je družina ?$\Gamma_n (1^s)$? podgrafov, induciranih z nizi, ki so brez ?$1^s$? kot podniza, pri čemer je ?$s \geq 2$? dano celo število. V prejšnjem članku smo dokazali obstoj popolne kode v ?$\Gamma_n (1^s)$? za ?$n = 2^p - 1$? in ?$s \geq 3.2^{p-2}$? za vsako celo število ?$p \geq 2$?. Lucasovo kocko ?$\Lambda_n$? dobimo iz ?$\Gamma_n$? z odstranitvijo vozlišč, ki se začnejo in končajo z 1. Pogosto so isti problemi preučevani na Fibonaccijevih kockah in na Lucasovi kocki. V tem kratkem članku dokažemo neobstoj popolnih kod v ?$\Lambda_n$? za ?$n \geq 4$? in dokažemo eksistenco popolnih kod v nekaterih posplošenih Lucasovih kockah ?$\Lambda_n (1^s)$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije