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

angleški

2022

letnik 22, številka 3

Fibonaccijeva kocka   kode za popravljanje napak   popolna koda

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

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)$?.

22.11.2022