1.
k-Domination ivariants on Kneser graphsBoštjan Brešar,
Tanja Dravec,
María Gracia Cornet,
Michael A. Henning, 2025, original scientific article
Abstract: 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)) ≥ γ_k(K(n + 1, r)) holds for any n ≥ 2(k + r), and γ_{t × k}(K(n, r)) ≥
γ_{t × k}(K(n + 1, r)) holds for any n ≥ 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 ≥ 2. Concerning the 2-packing number, ρ₂(K(n, r)), of K(n, r), we prove the exact values of ρ₂(K(3r − 3, r)) when r ≥ 10, and give sufficient conditions for ρ₂(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: Kneser graphs, k-domination, k-tuple total domination, 2-packing
Published in RUP: 22.10.2025; Views: 195; Downloads: 1
Full text (375,34 KB)
