k-domination invariants on Kneser graphs - Brešar, Boštjan (Ars mathematica contemporanea, 2025)
Članek je nadaljevanje članka M.G. Cornet, P. Torres, arXiv:2308.15603, v katerem sta avtorja raziskovala ?$k$?-terno dominacijsko število in ?$2$?-pakirno število Kneserjevih grafov ?$K(n,r)$?. Nas zanimata dve sorodni inačici, namreč ?$k$?-dominacijsko število ?$γ_k(K(n,r))$? in ?$k$?-terno celotno dominacijsko število ?$γ_{t× k}(K(n,r))$? Kneserjevih grafov ?$K(n,r)$?. Za obe invarianti dokažemo neko vrsto monotonosti in sicer, da za vse ?$n\ge 2(k+r)$? velja ?$γ_k(K(n,r))\ge γ_k(K(n+1,r))$? ter da za vse ?$n\ge 2r+1$? velja ?$γ_{t× k}(K(n,r))\ge γ_{t× k}(K(n+1,r))$?. Dokažemo tudi, da velja ?$γ_k(K(n,r))=γ_{t× k}(K(n,r))=k+r$?, če je ?$n≥ r(k+r)$?, in da je v tem primerih vsaka ?$γ_k(K(n,r))$?-množica in ?$γ_{t× k}$?-množica klika. Po drugi strani dokažemo, da velja ?$γ_k(r(k+r)-1,r)=γ_{t× k}(r(k+r)-1,r)=k+r+1$? za vsak ?$k\ge 2$?. Glede ?$2$?-pakirnega števila ?$ρ_2(K(n,r))$? grafa ?$K(n,r)$? določimo točne vrednosti ?$ρ_2(K(3r-3,r))$?, ko je ?$r\ge 10$? in podamo zadostne pogoje v obliki mej za število ?$r$? glede na število ?$n$?, ki zagotavljajo, da je ?$ρ_2(K(n,r))$? enako nekim predpisanim majhnim vrednostim. Dokažemo tudi neko vrsto monotonosti za ?$2$?-pakirno število Kneserjevih grafov.
Keywords: 2-packing; 2-pakiranje; k-dominacija; k-domination; Kneser graphs; Kneserjev graf; k-terna celotna dominacija; k-tuple total domination