$k$-tuple domination on Kneser graphs

María Gracia Cornet, Pablo Torres

Published 2023-08-29Version 1

In this paper, we continue the study of different types of dominating sets in Kneser graphs. We focus on $k$-tuple dominating sets, $2$-packings and the associated graph parameters $k$-tuple domination number and $2$-packing number. In particular, we determine the Kneser graphs $K(n,r)$ with $k$-tuple domination number exactly $k+r$ and find all the minimum sized $k$-tuple dominating sets for these graphs, which generalize results for dominating sets in Kneser graphs. Besides, we give a characterization of the $k$-tuple dominating sets of $K(n,2)$ in terms of the occurrences of the elements in $[n]$, which allows us to obtain minimum sized $k$-tuple dominating sets for almost all positive integers $n\geq 4$. Finally, we compute both parameters for certain Kneser graphs, and specifically in odd graphs we show that these invariants are extremely related with perfect $1$-codes and Steiner systems. Keywords: Kneser graphs, $k$-tuple dominating set.