k-domination invariants on Kneser graphs - Brešar, Boštjan (Ars mathematica contemporanea, 2025)
In this follow-up to work of M.G. Cornet and P. Torres from 2023, where the ?$k$?-tuple domination number and the ?$2$?-packing number in Kneser graphs ?$K(n,r)$? were studied, we are concerned with two variations, the ?$k$?-domination number, ?$γ_k(K(n,r))$?, and the ?$k$?-tuple total domination number, ?$γ_{t× k}(K(n,r))$?, of ?$K(n,r)$?. For both invariants we prove monotonicity results by showing that ?$γ_k(K(n,r))\ge γ_k(K(n+1,r))$? holds for any ?$n\ge 2(k+r)$?, and ?$γ_{t× k}(K(n,r))\ge γ_{t× k}(K(n+1,r))$? holds for any ?$n\ge 2r+1$?. We prove that ?$γ_k(K(n,r))=γ_{t× k}(K(n,r))=k+r$? when ?$n≥ r(k+r)$?, and that in this case every ?$γ_k$?-set and ?$γ_{t× k}$?-set is a clique, while ?$γ_k(r(k+r)-1,r)=γ_{t× k}(r(k+r)-1,r)=k+r+1$?, for any ?$k\ge 2$?. Concerning the ?$2$?-packing number, ?$ρ_2(K(n,r))$?, of ?$K(n,r)$?, we prove the exact values of ?$ρ_2(K(3r-3,r))$? when ?$r\ge 10$?, and give sufficient conditions for ?$ρ_2(K(n,r))$? to be equal to some small values by imposing bounds on ?$r$? with respect to ?$n$?. We also prove a version of monotonicity for the ?$2$?-packing number of Kneser graphs.
Keywords: 2-packing; 2-pakiranje; k-dominacija; k-domination; Kneser graphs; Kneserjev graf; k-terna celotna dominacija; k-tuple total domination