On k-tuple domination on Kneser graphs

MARÍA GRACIA CORNET

Maribor

Workshop; Seminario de Matemáticas Discretas (Seminar iz diskretne matematike); 2023

Universidad de Maribor

In this work, we continue the study of different types of dominating sets on Kneser graphs. We focus on $k$-tuple dominating sets, $2$-packings and the associated graph parameters $k$-tuple domination number and $2$-packing number.% A $k$-tuple dominating set is a subset of vertices that meets each closed neighbourhood in at least $k$ vertices and a $2$-packing is a subset of vertices with pairwise disjoint closed neighbourhoods.In particular, we determine the Kneser graphs $\Kneser{n}{r}$ with $k$-tuple domination number exactly $k+r$ and find all the minimum $k$-tuple dominating sets for these graphs, which generalize results for dominating sets on Kneser graphs. Besides, we give a characterization of the $k$-tuple dominating sets of $\Kneser{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\geq4$. Finally, we compute the $k$-tuple domination number and $2$-packing number for certain Kneser graphs, and specifically in odd graphs we show that these invariants are closely connected to perfect $1$-codes and Steiner systems.