On domination-type invariants of Fibonacci cubes and hypercubes

angleški

2018

letnik 14, številka 2

celoštevilsko linearno programiranje   celotno dominantno število   Fibonaccijeva kocka   hiperkocka   pokrivne kode

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

Fibonaccijeva kocka ?$\Gamma_n$? je podgraf ?$n$?-dimenzionalne kocke ?$Q_n$? induciran z vozlišči, ki ne vsebujejo dveh zaporednih enic. S pomočjo celoštevilskega linearnega programiranja določimo točne vrednosti za ?$\gamma_t(\Gamma_n)$?, ?$n\le 12$?. Kot posledico dokažemo, da za vse ?$n\ge 11$? velja ?$\gamma_t(\Gamma_{n})\le 2F_{n-10} + 21F_{n-8}$?, kjer so ?$F_n$? Fibonaccijeva števila. Dokazano je tudi, da če je ?$n\ge 9$?, potem velja ?$\gamma_t(\Gamma_{n}) \ge \left\lceil (F_{n+2}-11)/(n-3)\right\rceil - 1$?. S pomočjo celoštevilskega linearnega programiranja so določene točne vrednosti za 2-pakirno število, povezano dominantno število, dvojno dominantno število in predznačeno dominantno število majhnih Fibonaccijevih kock in hiperkock. Domneva za celotno dominantno število hiperkock, ki trdi, da za vse ?$n \geq 6$? velja ?$\gamma_t(Q_n) = 2^{n-2}$?, je ovržena na več različnih načinov.

29.05.2020