#  $k$-tuple domination on Kneser graphs 111Partially supported by PIP CONICET
1900, PICT-2020-03032 and PID 80020210300068UR.

Maria Gracia Cornet 222e-mail<EMAIL_ADDRESS>Depto. de Matemática,
Facultad de Ciencias Exactas, Ing. y Agrimensura, Universidad Nacional de
Rosario Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina
Pablo Torres 333e-mail<EMAIL_ADDRESS>Depto. de Matemática,
Facultad de Ciencias Exactas, Ing. y Agrimensura, Universidad Nacional de
Rosario Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina

###### Abstract

This paper considers multiple domination 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. In particular, we compute
the $2$-packing number of Kneser graphs $K({3r-2,r})$ and in odd graphs we
obtain minimum $k$-tuple dominating sets of $K(7,3)$ and $K(11,5)$ for every
$k$. Besides, we determine the Kneser graphs $K({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 domination on Kneser
graphs. Finally, 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 of $K({n,2})$ for
$n\geq\Omega(\sqrt{k})$.
Keywords: Kneser graphs, multiple domination, $k$-tuple domination,
$2$-packings.

##  1 Introduction

Given a simple graph $G$, let $N_{G}\left({v}\right)$ denote the _open
neighbourhood_ of a vertex $v$ in $G$ and
$N_{G}\left[{v}\right]=N_{G}\left({v}\right)\cup\\{v\\}$ the _closed
neighbourhood_ of $v$ in $G$. When the graph $G$ is clear from the context, we
may omit the subscripts and simply write $N\left({v}\right)$ and
$N\left[{v}\right]$. Furthermore, let $\delta\left({G}\right)$ be the _minimum
degree_ among all the vertices of graph $G$. Other definitions not given here
can be found in standard graph theory books such as [39]. A _dominating set_
in $G$ is a subset $D\subseteq V(G)$ such that every vertex $v\in V(G)$
verifies that $|N[v]\cap D|\geq 1$. The _domination number_ of $G$, denoted
$\gamma\left(G\right)$, is the minimum cardinality of a dominating set in $G$.
Domination in graphs has been extensively studied in graph theory, and there
is rich literature on this subject (see e.g. [22, 24, 23]).

Some of the most studied variations of domination introduced a variable
$k\in\mathbb{N}$, such as $k$-tuple domination. Formally, given a graph $G$
and $k\in\mathbb{N}$, a set $D\subseteq V(G)$ is called a _$k$ -tuple
dominating set_ of $G$ if for every vertex $v\in V(G)$, we have
$|N_{G}\left[{v}\right]\cap D|\geq k$. The _$k$ -tuple domination number_ of
$G$ is the minimum cardinality of a $k$-tuple dominating set of $G$, and is
denoted by $\gamma_{\times k}\left(G\right)$. A _$\gamma_{\times k}$ -set_ is
a $k$-tuple dominating set with cardinality $\gamma_{\times k}\left(G\right)$.
The $k$-tuple domination number is only defined for graphs with
$\delta\left({G}\right)\geq k-1$. An excellent brief survey on $k$-tuple
domination appears in the book Topics in Domination in Graphs [22], as part of
a chapter devoted to the study of multiple domination.

Several bounds for the $k$-tuple domination number of graphs are given in [7,
37, 41, 9, 15, 35]. Liao and Chang [30] studied the problem from an
algorithmic point of view and proved that, fixed $k$, determining the
$k$-tuple domination number is NP-complete for split graphs and for bipartite
graphs. Considering these unfavourable outcomes, exploring how this parameter
behaves within classes of graphs exhibiting a nice combinatorial structure,
like Kneser graphs, represents a natural direction for further research. In
addition, another goal of this paper is to contribute to a deeper
understanding on Kneser graphs. For instance, in Section 2 we show that
$k$-tuple dominating sets in Kneser graphs are closely related to interesting
combinatorial incidence structures like $2$-packings [33] in graphs, codes [3]
in graphs and intersecting set systems (e.g., Fano plane and Steiner systems).

For positive integers $r,n$ with $n\geq 2r$, the _Kneser graph_ $K({n,r})$ has
as vertices the $r$-subsets of an $n$-set and two vertices are adjacent in
$K({n,r})$ if and only if they are disjoint. This class of graphs gained
prominence due to the Erdős-Ko-Rado theorem [13], which determined the
independence number $\alpha(K({n,r}))$ of the Kneser graph $K({n,r})$ to be
$\binom{n-1}{r-1}$, as a result on extremal combinatorics. Lovász’s proof of
Kneser’s conjecture [31, 29], later complemented by Matoušek’s combinatorial
proof [32], provided a determination of the chromatic number of Kneser graphs.
Numerous other graph invariants have been investigated on Kneser graphs by
various authors [21, 14, 16, 2]. One of them is the domination number [20, 26,
34, 17]. In particular, the value of the domination number of $K({n,r})$ is
determined for $n$ large enough in Theorem 1.

Figure 1: Kneser graph $K({5,2})$

######  Theorem 1.

[34, Theorem 2.2] If $n\geq r^{2}+r$, then
$\gamma\left(K({n,r})\right){}=r+1$.

It is also known that $\gamma\left(K({n,2})\right){}=3$ for $n\geq 4$ [26].
Furthermore, for the remaining cases of Kneser graphs partial results are
provided, but a complete solution for the domination number, similar to the
case of chromatic and independence numbers, has not yet been achieved.

After these results, different variations of domination have been explored on
Kneser graphs. For instance, in 2019 Brešar et al. [5] studied four different
types of Grundy domination numbers and the related zero forcing numbers on
Kneser graphs. In 2023, P. Jalilolghadr and A. Behtoei computed the total
dominator chromatic number of the Kneser graph $K({n,2})$ for each $n\geq 5$.
Also in 2023, three Roman domination graph invariants on Kneser graphs are
studied by T. Zec and M. Grbić [40]. They obtained the exact values of the
mentioned invariants for $K({n,2})$ and also for $K({n,r})$ if $n$ is large
enough with respect to $r$. A closely related concept to $k$-tuple domination
is _$k$ -domination_. Given a graph $G$ and $k\in\mathbb{N}$, a set
$D\subseteq V(G)$ is a _$k$ -dominating set_ if for every vertex $u\notin D$
it holds $|N[u]\cap D|\geq k$. The _$k$ -domination number_ of a graph $G$ is
the minimum cardinality of a $k$-dominating set of $G$. Results on
$k$-domination for Kneser graphs appear in [6] after a first version of the
present paper [12] was released.

As we have mentioned, in this work we focus on the study of $k$-tuple
domination on Kneser graphs. In Section 2 we analyze $k$-tuple dominating sets
of Kneser graphs, from its relationship with $2$-packings in graphs. We show
that $2$-packings on Kneser graphs are closely connected to intersecting set
families. Using this link, we compute the $2$-packing number of $K({n,r})$ for
$n=3r-2$ and $r\geq 3$. Then we obtain $\gamma_{\times k}$-sets for the odd
graphs $K({7,3})$ and $K({11,5})$ for every $k$, from the Steiner systems
$S(2,3,7)$ (Fano plane) and $S(4,5,11)$ respectively. Furthermore, in the case
of $K({7,3})$, we give all the $\gamma_{\times k}$-sets.

In Section 3 we generalize the result in Theorem 1 (notice that
$\gamma_{\times 1}\left(G\right)=\gamma\left(G\right)$) by proving that
$\gamma_{\times k}\left(K({n,r})\right)=k+r$ if and only if $n\geq r(k+r)$ and
we characterize the $\gamma_{\times k}$-sets for these cases. Besides, we
prove that $\gamma_{\times k}\left(K({n,r})\right)$ is not decreasing with
respect to $n$, so we conclude that $\gamma_{\times k}\left(K({n,r})\right)$
is at least $k+r+1$ if $n<r(k+r)$. In addition, we calculate $\gamma_{\times
k}\left(K({n,r})\right)$ for $k$ large enough.

Finally, in Section 4 we give a characterization of the $k$-tuple dominating
sets for $K({n,2})$ that lead us to provide $\gamma_{\times
k}\left(K({n,2})\right)$ for $k\leq a\,\frac{n-3}{4}$, with $a=n-4$ if $n$ is
even and $a=n-6+(n\ mod\ 4)$ if $n$ is odd. We also design an ILP formulation
to obtain some $k$-tuple dominating sets whose cardinality meet the lower
bounds given previously. Table 1 shows the results for $n\leq 26$ and $k\leq
60$.

##  2 $2$-packings and $k$-tuple dominating sets on odd graphs

Packings and dominating sets have been extensively studied in graphs. In this
regard, $2$-packings have been received particular attention and determining
the $2$-packing number of classes of graphs is a challenging and interesting
topic, see e.g. [28, 4, 10, 8]. Given a graph $G$, a subset $S\subseteq V(G)$
is called a _$2$ -packing_ of $G$ if for every pair of vertices $u,v\in S$,
their closed neighborhoods satisfy $N\left[{u}\right]\cap
N\left[{v}\right]=\emptyset$. In other words, no two vertices in the
$2$-packing have any common neighbor. The _$2$ -packing number_ of a graph
$G$, denoted by $\rho\left(G\right)$, is the maximum cardinality of a
$2$-packing in $G$. In [7], the author establishes a relationship between the
$2$-packing number and the $k$-tuple domination number.

######  Theorem 2.

[7, Theorem 2.3] Let $k\geq 2$ be an integer. For any graph $G$ of order $n$
and $\delta\left({G}\right)\geq k$,

$k\rho\left(G\right)\leq\gamma_{\times k}\left(G\right)\leq
n-\rho\left(G\right).$

It is known that when $n\geq 3r-1$ with $r\geq 2$, the diameter of the Kneser
graph $K({n,r})$ is equal to $2$ [38]. Therefore, in these cases the
$2$-packing number of the Kneser graph $K({n,r})$ is equal to $1$. Thus, for
the remaining of this section, we consider $2r+1\leq n\leq 3r-2$. Similarly to
other works on domination on Kneser graphs, we use $\rho\left(n,r\right)$ to
denote the $2$-packing number of the Kneser graph $K({n,r})$, and
$\gamma_{\times k}\left(n,r\right)$ to denote the $k$-tuple domination number
of the Kneser graph $K({n,r})$. For positive integers $r\leq n$, we denote by
$[r..n]$ and $[n]$ the sets $\\{r,\ldots,n\\}$ and $\\{1,\ldots,n\\}$,
respectively.

Let $S$ be a $2$-packing in $K({n,r})$. If $u$ and $v$ are two vertices in $S$
then $u\cap v\neq\emptyset$. Besides, notice that if $|u\cap v|>(3r-1)-n$,
then

$|[n]\setminus(u\cup v)|=|[n]|-|u|-|v|+|u\cap v|\geq r,$

This implies that there exists a vertex $w\in N\left({u}\right)\cap
N\left({v}\right)$, contradicting the fact that $S$ is a $2$-packing.

######  Remark 3.

Let $2r+1\leq n\leq 3r-2$. A set $S$ of $r$-subsets of $[n]$ is a $2$-packing
of $K({n,r})$ if and only if for every pair $u,v\in S$, it holds that

$1\leq|u\cap v|\leq(3r-1)-n.$

Some results on extremal combinatorics and intersecting families can be used
to give upper bounds for the $2$-packing number of Kneser graphs. In fact,
from [36], we have:

$\rho\left(n,r\right)\leq\binom{n}{(3r-1)-n}$

and

$\rho\left(n,r\right)\leq\sum_{i=0}^{(3r-1)-n}\binom{n-1}{i}.$

In the case $n=3r-2$ both bounds remain

$\rho\left(n,r\right)\leq n,$

which is tight only for $r=3$, as we will show in Theorem 4.

We introduce the following notation, which will be used throughout the paper.
Given a set of vertices $D$ in $K({n,r})$ and $x\in[n]$, the occurrences of
the element $x$ in $D$, denoted by $i_{x}(D)$, represent the number of
vertices in $D$ that contain the element $x$. In other words, $i_{x}(D)$ is
the cardinality of the set $\\{u\in D:x\in u\\}$. For a positive integer $a$,
we define $X_{a}(D)$ as the set of elements in $[n]$ such that their
occurrences in $D$ are equal to $a$, i.e.,
$X_{a}(D)=\\{x\in[n]:i_{x}(D)=a\\}$. Similarly, we define
$X_{a}^{\geq}(D)=\\{x\in[n]:i_{x}(D)\geq a\\}$, and
$X_{a}^{\leq}(D)=\\{x\in[n]:i_{x}(D)\leq a\\}$. When the set $D$ is clear from
the context, we shall omit it in the notation. It is important to note that
the sum of the occurrences of all elements in $D$ is equal to $r$ times the
cardinality of $D$, i.e., $\sum_{x\in[n]}i_{x}=r|D|$.

######  Theorem 4.

If $n=3r-2$ and $r\geq 3$, then

$\rho\left(n,r\right)=\begin{cases}7,&\text{if }r=3,\\\ 5,&\text{if }r=4,\\\
3,&\text{if }r\geq 5.\end{cases}$ (1)

###### Proof.

Let $r\geq 3$, $n=3r-2$ and let $S$ be a $2$-packing of $K({n,r})$. From
Remark 3, we have that for every pair of vertices $u,v\in S$, it holds $|u\cap
v|=1$.

Let us see that $i_{x}\leq 3$ for every $x\in[n]$. In fact, suppose $i_{a}\geq
4$ for some $a\in[n]$, and let $u_{1},u_{2},u_{3},u_{4}$ be four vertices in
$S$ such that $a\in u_{j}$ for $j\in[4]$. We have
$|u_{j}\setminus\\{a\\}|=r-1$ and
$\left(u_{j}\setminus\\{a\\}\right)\cap\left(u_{\ell}\setminus\\{a\\}\right)=\emptyset$
for $j,\ell\in[4]$ with $j\neq\ell$. Then

$n\geq\left|\bigcup_{j=1}^{4}u_{j}\right|=1+\sum_{j=1}^{4}\left|u_{j}\setminus\\{a\\}\right|=4r-3=n+\underbrace{r-1}_{>0},$

which cannot be true. Thus, $i_{x}\leq 3$ for every $x\in[n]$. Then we have
$|S|\leq\dfrac{3n}{r}$.

If $r=3$, then $n=7$ and the cardinality of a $2$-packing $S$ is at most $7$.
In fact, a set of $7$ $3$-subsets of $[7]$ which mutually intersect in exactly
one element, is a Fano plane (see Figure 2). Thus, we have
$\rho\left(7,3\right)=7$.

$6$$4$$7$$1$$3$$2$$5$ Figure 2: An maximum $2$-packing in $K({7,3})$ and the
corresponding Fano plane

If $r\geq 4$, let us suppose that $i_{a}=3$ for some $a\in[n]$ and let the
vertices $u_{1},u_{2},u_{3}\in S$ be such that $a\in u_{j}$ for each $j$.
Without loss of generality, let us consider $a=1$ and

$u_{1}=\\{1\\}\cup[2..r],\qquad u_{2}=\\{1\\}\cup[r+1..2r-1],\qquad
u_{3}=\\{1\\}\cup[2r..3r-2].$

Let $w$ be another vertex in $S$. $1\notin w$ since $i_{1}$ is exactly $3$.
Then $w=\\{a_{1},\ldots,a_{r}\\}$ with $a_{j}\in[n]\setminus\\{1\\}$ for
$j\in[r]$. Since $\left\\{u_{i}\setminus{\\{1\\}}\right\\}_{i=1}^{3}$ is a
partition of $[n]\setminus{\\{1\\}}$, and $r\geq 4$, by the pigeonhole
principle there exist at least two elements $a_{j}$ and $a_{\ell}$ that
belongs to $u_{k}$ for some $k\in[3]$. This is, $|u_{k}\cap w|\geq 2$ but this
leads to a contradiction with the fact that $S$ is a $2$-packing.

Therefore, if there exists $a\in[n]$ such that $i_{a}=3$, then $|S|\leq 3$. On
the contrary, if $i_{a}\leq 2$ for every $a\in[n]$, we have
$|S|\leq\dfrac{2n}{r}$.

If $r=4$, then $n=10$ and the cardinality of a $2$-packing $S$ is at most $5$.
In fact, we have $\rho\left(10,4\right)=5$ and if $S$ is an maximum
$2$-packing of $K({10,4})$, then, up to automorphism, we have
$S=\big{\\{}\\{1,2,3,4\\},\\{1,5,6,7\\},\\{2,5,8,9\\},\\{3,6,8,10\\},\\{4,7,9,10\\}\big{\\}}$.

If $r\geq 5$, suppose that $i_{a}\leq 2$ for every $a\in[n]$. Let
$u_{1},u_{2},u_{3}\in S$. Without loss of generality, we may assume that

$u_{1}=\\{1,2\\}\cup[4..r+1],\qquad u_{2}=\\{1,3\\}\cup[r+2..2r-1],\qquad
u_{3}=\\{2,3\\}\cup[2r..3r-3].$

A fourth vertex in $S$ must contain exactly one element from each set
$u_{1},u_{2},u_{3}$ and two elements from $[n]\setminus\left(u_{1}\cup
u_{2}\cup u_{3}\right)$. However,

$\left|[n]\setminus\left(u_{1}\cup u_{2}\cup
u_{3}\right)\right|=(3r-2)-(3r-3)=1.$

We can conclude that $|S|\leq 3$, and $S=\\{u_{1},u_{2},u_{3}\\}$ is a
$2$-packing of maximum cardinality.

Therefore, if $r\geq 5$, $\rho\left(3r-2,r\right)=3$. ∎

As a by-product of the previous proof, we have the following result.

######  Corollary 5.

If $n=3r-2$ with $r\geq 5$, and $S$ is an maximum $2$-packing of $K({n,r})$,
then up to automorphism we have

$S=\big{\\{}\\{1,2\\}\cup[4..r+1],\\{1,3\\}\cup[r+2..2r-1],\\{2,3\\}\cup[2r..3r-3]\big{\\}},$

or

$S=\big{\\{}\\{1\\}\cup[2..r],\\{1\\}\cup[r+1..2r-1],\\{1\\}\cup[2r..3r-2]\big{\\}}.$

Let us notice that $2$-packings on Kneser graphs are related to Steiner
systems. A Steiner system $S(t,r,n)$ is a collection of $r$-subsets of $[n]$,
called blocks, with the property that each $t$-subset of $[n]$ is contained in
exactly one block. It is not hard to see that for $2r+1\leq n\leq 3r-2$, if a
Steiner system $S(3r-n,r,n)$ exists, then

$\rho\left(n,r\right)\leq|S(3r-n,r,n)|.$

This relationship is useful to study $2$-packings in odd graphs. To this end,
we consider perfect $1$-codes in graphs [19]. A subset of vertices $C$ of a
graph $G$ is a perfect $1$-code of $G$ if the family of closed neighbourhood
$\left\\{N[v]\right\\}_{v\in C}$ is a partition of $V(G)$. Notice that if a
perfect $1$-code of a graph $G$ exists, then it is also an maximum $2$-packing
of $G$. In particular, it is known [19] that a set $C$ is a Steiner system
$S(r-1,r,2r+1)$ if and only if $C$ is a perfect $1$-code in the odd graph
$K({2r+1,r})$. Thus, the case $r=3$ in Theorem 4 also follows from the fact
that the Fano plane is a Steiner system $S(2,3,7)$. Similarly, since a Steiner
system $S(4,5,11)$ exists [1], then the odd graph $K({11,5})$ has a perfect
$1$-code and

$\rho\left(11,5\right)=66.$

The well known conjecture due to Biggs [3] asserts that there is no perfect
$1$-code if $r\neq 3,5$. Although it has been verified for some values of $r$,
it has not yet been settled in general. For an exhaustive study of Steiner
systems we refer to [11] and references therein.

Notice that the existence of a perfect $1$-code of the odd graph $K({2r+1,r})$
gives the following lower bound for the $k$-tuple domination number

$\gamma_{\times k}\left(2r+1,r\right)\geq
k\rho\left(2r+1,r\right)=\frac{\binom{2r+1}{r}\,k}{r+2}$

which we will show is tight for $r=3,5$ and each $k$.

######  Lemma 6.

Let $G$ be a vertex-transitive graph. If $\gamma_{\times
k}\left(G\right)=k\rho\left(G\right)$ and $D$ is a $\gamma_{\times k}$-set,
then it holds $|N[v]\cap D|=k$ for every $v\in V(G)$.

###### Proof.

Let $S$ be an maximum $2$-packing and $D$ a $\gamma_{\times k}$-set of $G$.
Notice that $|N[u]\cap D|\geq k$ for every vertex $u$ as $D$ is a $k$-tuple
dominating set. On the other hand, the sets $\\{N[u]\\}_{u\in S}$ are pairwise
disjoint. So, we have

$\gamma_{\times k}\left(G\right)=|D|\geq\sum_{u\in S}\underbrace{|N[u]\cap
D|}_{\geq k}\geq k|S|=k\rho\left(G\right)=\gamma_{\times k}\left(G\right).$
(2)

In consequence, $|N[u]\cap D|=k$ for every $u\in S$.

Besides, let $v\in V(G)$. Since $G$ is a vertex-transitive graph, it is
possible to find an maximum $2$-packing $S^{\prime}$ such that $v\in
S^{\prime}$. Thus, $|N[v]\cap D|=k$. ∎

As it is well-known that Kneser graphs are vertex-transitive graphs, we have
that if $\gamma_{\times k}\left(n,r\right)=k\rho\left(n,r\right)$ and $D$ is a
$\gamma_{\times k}$-set of $K({n,r})$, then $|N[u]\cap D|=k$ for every $u\in
V(K({n,r}))$.

######  Remark 7.

Let us notice that if $D_{k}$ is a $k$-tuple dominating set of $K({n,r})$ with
cardinality $|D_{k}|=k\rho\left(n,r\right)$, then the set
$V(K({n,r}))\setminus D_{k}$ is a $\tilde{k}$-tuple dominating set of
$K({n,r})$, with $\tilde{k}=\binom{n-r}{r}+1-k$. In fact, for every vertex
$u\in V(K({n,r}))$, by Lemma 6 we have

$|N[u]\cap(V(K({n,r}))\setminus
D_{k})|=\underbrace{|N[u]|}_{\binom{n-r}{r}+1}-\underbrace{|N[u]\cap
D_{k}|}_{k}=\binom{n-r}{r}+1-k.$

It is known that there exist exactly two disjoint Fano planes. Thus the union
of these two Fano plane is a $\gamma_{\times 2}$-set of $K({7,3})$. Moreover,
we provide $\gamma_{\times k}$-sets of $K({7,3})$ for each $k\in[5]$.

######  Remark 8.

For $r=3$ and $n=7$, from Theorem 4 it turns out that
$\rho\left(7,3\right)=7$. A bound for $\gamma_{\times k}\left(7,3\right)$ is
given by Theorem 2 and we have $\gamma_{\times k}\left(7,3\right)\geq 7k$. In
fact, for these values of $n$ and $r$ we shall see that this bound is tight
and we have $\gamma_{\times k}\left(7,3\right)=7k$ for $1\leq k\leq 5$.

Figure 3: A $\gamma_{\times 2}$-set of $K({7,3})$

It is enough to consider two disjoint Fano Planes $F_{1},F_{2}$ and the sets

$D_{1}=F_{1},\qquad D_{2}=F_{1}\cup F_{2},\qquad D_{3}=V\setminus D_{2},\qquad
D_{4}=V\setminus D_{1},\qquad D_{5}=V,$

where $V=V(K({7,3}))$. For each $k\in[5]$, $D_{k}$ turns out to be a $k$-tuple
dominating set with cardinality $|D_{k}|=7k$ and in consequence is a
$\gamma_{\times k}$-set.

In Remark 8 we provide $\gamma_{\times k}$-sets of $K({7,3})$. In fact, by
exhaustive methods we can prove that these sets are unique up to automorphism.
Regarding Steiner systems $S(4,5,11)$, it is also known that there are exactly
two disjoint such Steiner systems. We know that the union of them is a
$\gamma_{\times 2}$-set of $K({11,5})$. We also find, for $k\in\\{3,4,5,6\\}$,
a $\gamma_{\times k}$-set of $K({11,5})$ (see Appendix A). Although this
parallelism with the case $K({7,3})$, we do not known if the given
$\gamma_{\times k}$-sets of $K({11,5})$ are unique up to automorphism for
$k\in\\{2,3,4,5\\}$.

##  3 General results on $k$-tuple domination on Kneser graphs

We note that the bounds for the $k$-tuple domination number given in Theorem 2
are not tight in general. For example, as we have mentioned,
$\rho(K({n,r}))=1$ if $n\geq 3r-1$, but $\gamma_{\times
1}\left(n,r\right)=\gamma\left(K({n,r})\right)\geq r+1$ for $n\geq r^{2}+r$.
Also, the known general bounds for $k$-tuple domination number of graphs [7,
9, 15, 37] are not efficient to determine the $\gamma_{\times
k}\left(n,r\right)$ for $n\geq 2r+1$. Moreover, some of these upper bounds
applied to $\gamma_{\times k}\left(n,r\right)$ are increasing with respect to
$n$ whereas, as we will prove in Theorem 12, the parameter $\gamma_{\times
k}\left(n,r\right)$ is decreasing with respect to $n$. Therefore, in this
section we will apply properties of Kneser graphs to study $k$-tuple
dominating sets on $K({n,r})$ for $n$ large enough.

Since Kneser graphs are regular graphs and each vertex in $K({n,r})$ has
degree $\binom{n-r}{r}$, then the Kneser graph $K({n,r})$ can only have a
$k$-tuple dominating set if $k\leq\binom{n-r}{r}+1$. Furthermore, if
$k=\binom{n-r}{r}+1$, the entire set of vertices in $K({n,r})$ is the only
$k$-tuple dominating set. The Kneser graph $K({n,1})$ is isomorphic to the
complete graph $K_{n}$. In this case, $\gamma_{\times k}\left(n,1\right)=k$
for $k\in[n]$. On the other hand, if $n=2r$, then the Kneser graph $K({2r,r})$
is isomorphic to $\frac{1}{2}\binom{2r}{r}$ copies of $K_{2}$. It is
noteworthy that $\gamma_{\times 1}\left(2r,r\right)=\frac{1}{2}\binom{2r}{r}$,
$\gamma_{\times 2}\left(2r,r\right)=\binom{2r}{r}$, and no $k$-tuple
dominating set exists for these graphs if $k\geq 3$. Thus, for the subsequent
discussion, we consider $n\geq 2r+1$ and $r\geq 2$.

In Theorem 1 it is shown that if $n\geq r^{2}+r$, then $\gamma_{\times
1}\left(n,r\right)=\gamma\left(K({n,r})\right){}=r+1$. Moreover, for every $k$
we state the following result.

######  Lemma 9.

If $n\geq r(k+r)$, then $\gamma_{\times k}\left(n,r\right)=k+r$.

###### Proof.

Let $D=\\{u_{1},\ldots,u_{k+r}\\}$ be a set of vertices of $K({n,r})$ such
that $u_{i}\cap u_{j}=\emptyset$ for all $i\neq j$. It is possible since
$n\geq r(k+r)$. Consider a vertex $u$ of $K({n,r})$. If $u\in D$, then there
exists $i\in\\{1,\ldots,k+r\\}$ such that $u=u_{i}$. Since $u\cap
u_{j}=\emptyset$ for all $j\neq i$, we have $D\setminus\\{u_{i}\\}\subseteq
N(u)$. Thus,

$|D\cap N[u]|=|D|=k+r\geq k.$

If $u\notin D$, we have $|\\{i:u_{i}\cap u\neq\emptyset\\}|\leq r$. So

$|D\cap N[u]|\geq|D|-r=k.$

Therefore $D$ is a $k$-tuple dominating set of $K({n,r})$ with cardinality
$k+r$, and $\gamma_{\times k}\left(n,r\right)\leq k+r$.

Now, assume that there exists a $k$-tuple dominating set $D$ with cardinality
$|D|=k+r-1$. Let us consider $r$ distinct vertices $u_{1},\ldots,u_{r}$ of
$D$. Let $a_{1}\in u_{1}$ and for each $2\leq i\leq r$ we choose $a_{i}\in
u_{i}$ such that $a_{i}\notin\\{a_{1},\ldots,a_{i-1}\\}$. Let
$w=\\{a_{1},\ldots,a_{r}\\}$. If $w\neq u_{i}$ for every $i\in[r]$, then we
have $w\cap u_{i}\neq\emptyset$, and so $u_{i}\notin N[w]$ for all $i\in[r]$.
It turns out that

$|D\cap N[w]|\leq|D|-r\leq k-1,$

contradicting the fact that $D$ is $k$-tuple dominating.

If $w=u_{j}$ for some $j$, note that we can choose
$b\in[n]\setminus\left(\bigcup_{i=1}^{r}u_{i}\right)$. This choice is possible
since $|\bigcup_{i=1}^{r}u_{i}|\leq n-1$. In fact,
$u_{j}\subseteq\left(\bigcup_{i\neq j}u_{i}\right)\cup\\{a_{j}\\}$ and then

$\left|\bigcup_{i=1}^{r}u_{i}\right|\leq\left|\bigcup_{i\neq
j}u_{i}\right|+1\leq r(r-1)+1<r(k+r)\leq n.$

Let $w^{\prime}=\left[w\setminus\\{a_{j}\\}\right]\cup\\{b\\}$. We have
$w^{\prime}\neq u_{i}$ for every $i\in[r]$. Besides, $a_{i}\in w^{\prime}\cap
u_{i}$ for $i\neq j$, and $w^{\prime}\cap u_{j}=w\setminus\\{a_{j}\\}$.
Therefore $w^{\prime}\cap u_{j}\neq\emptyset$. Thus, $u_{i}\notin
N[w^{\prime}]$ for all $i\in[r]$. Then

$|D\cap N[w^{\prime}]|\leq|D|-r\leq k-1,$

contradicting the fact that $D$ is $k$-tuple dominating.

Therefore, it cannot exist a $k$-tuple dominating set of $K({n,r})$ with
cardinality less than $k+r$. We conclude that $\gamma_{\times
k}\left(n,r\right)=k+r$. ∎

Note that the condition $n\geq r(k+r)$ in Lemma 9 guarantees the existence of
a set of $k+r$ pairwise disjoint vertices of $K({n,r})$. In the next result,
we state that unless $k=1$ and $r=2$, this kind of set families characterizes
the $\gamma_{\times k}$-sets in $K({n,r})$ for these values of $n$.

######  Lemma 10.

Let $k\geq 2$ if $r=2$ and $k\geq 1$, otherwise. If $D$ is a $k$-tuple
dominating set of $K({n,r})$ with cardinality $k+r$, then the vertices of $D$
are pairwise disjoint.

###### Proof.

Let $D$ be a $k$-tuple dominating set of $K({n,r})$ with cardinality $k+r$.
Assume that the vertices in $D$ are not pairwise disjoint. Let $a\in[n]$ such
that $i_{a}=\max_{x\in[n]}i_{x}$. Under our assumption, $i_{a}\geq 2$.

If $i_{a}\geq 3$, let $u_{1},u_{2},u_{3}$ in $D$ such that $a\in u_{1}\cap
u_{2}\cap u_{3}$. Let us consider $u_{4},\ldots,u_{r+1}$ vertices in
$D\setminus\\{u_{1},u_{2},u_{3}\\}$. Let $b_{1}=a$. For $j=2,\ldots,r-1$, we
choose $b_{j}\in u_{j+2}\setminus\\{b_{1},\ldots,b_{j-1}\\}$. Let
$b=\\{b_{1},\ldots,b_{r-1}\\}$. Since $n\geq 2r+1$, it follows that
$|[n]\setminus b|=n-(r-1)\geq r+2$. Thus, there exists $x\in[n]$ such that
$w=b\cup\\{x\\}\neq u_{j}$ for $j=1,\ldots,r+1$. As a result, for every $j$ we
have $w\cap u_{j}\neq\emptyset$ and $w\neq u_{j}$. Then,

$|D\cap N[w]|\leq|D|-|\\{u_{1},\ldots,u_{r+1}\\}|=|D|-(r+1)=k-1,$ (3)

which contradicts the fact that $D$ is a $k$-tuple dominating set. So,
$i_{a}=2$.

Let $u_{1}$ and $u_{2}$ be the two vertices that contain the element $a$.

If $r>2$, let $u_{3},\ldots,u_{r+1}$ be vertices in
$D\setminus\\{u_{1},u_{2}\\}$. Let $b_{1}=a$ and for $j=2,\ldots,r$, we choose
$b_{j}\in u_{j+1}\setminus\\{b_{1},\ldots,b_{j-1}\\}$. Let
$w=\\{b_{1},\ldots,b_{r}\\}$. $b$ is a vertex that is not adjacent to any
$u_{j}$ for $j=1,\ldots,r+1$. If $w\neq u_{j}$ for each $j$, then it holds
(3), contradicting the fact that $D$ is $k$-tuple dominating. Then $w=u_{j}$
for some $j$. Since the only vertices that contain the element $b_{1}=a$ are
$u_{1}$ and $u_{2}$, without loss of generality, $w=u_{1}$. Then we have
$b_{j}\in u_{1}\cap u_{j+1}$ for every $j=1,\ldots,r$. Let $x\in
u_{2}\setminus w$ and let
$w^{\prime}=w\setminus\\{b_{1}\\}\cup\\{x\\}=\\{x,b_{2},\ldots,b_{r}\\}$. Let
us see that $w^{\prime}\neq u_{j}$ and $w^{\prime}\cap u_{j}\neq\emptyset$ for
every $j$. In fact, as $b_{j}\in u_{1}\cap u_{j+1}$ for $j=2,\ldots,r$, then
$w^{\prime}\cap u_{j}\neq\emptyset$ for every $j\in 1,\ldots,r+1$. Moreover,
if $w^{\prime}=u_{\ell}$ for some $\ell$, then since $a\notin w^{\prime}$,
$\ell\geq 3$ and for $j\neq\ell$, $j\geq 2$ we have that $b_{j-1}\in u_{1}\cap
u_{j}\cap u_{\ell}$. Thus, $i_{b_{j-1}}\geq 3$ but $\max_{x\in[n]}i_{x}=2$.
Therefore, $w^{\prime}\neq u_{j}$ for every $j$, and in consequence it holds
(3) for $w^{\prime}$.

If $r=2$, we have $u_{1}=\\{a,c\\}$, $u_{2}=\\{a,d\\}$ for some $c,d\in[n]$.
Since $k\geq 2$, there exists a vertex $u_{3}\in D\setminus\\{u_{1},u_{2}\\}$
such that $u_{3}\neq\\{c,d\\}$. Let $x\in u_{3}\setminus\\{c,d\\}$. Since
$i_{a}=2$, $x\neq a$. Consider the vertex $w=\\{a,x\\}$. We have $w\neq u_{j}$
and $w\cap u_{j}\neq\emptyset$ for every $j$. Then it holds (3).

Either if $r>2$ or $r=2$ we arise to a contradiction since $D$ is a $k$-tuple
dominating set.

Therefore, we conclude that the vertices in $D$ are pairwise disjoint. ∎

This result does not hold when $k=1$ and $r=2$. In fact, in [26] it is shown
that the dominating sets of $K({n,2})$ for $n\geq 5$ are the sets of $3$
vertices that are either pairwise disjoint or mutually intersecting.

As a by product of lemmas 9 and 10 we have the following result for $n$ large
enough.

######  Theorem 11.

For $k\geq 2$, $\gamma_{\times k}\left(n,r\right)=k+r$ if and only if $n\geq
r(k+r)$.

For $n<r(k+r)$ we will see that $\gamma_{\times k}\left(n,r\right)$ is greater
than $k+r$. To this end we observe monotonicity properties of the parameter
$\gamma_{\times k}\left(n,r\right)$ with respect to $k$ and $n$.

Note that if $D$ is a $(k+1)$-tuple dominating set of a graph $G$ and $v\in
D$, then $D\setminus\\{v\\}$ is a $k$-tuple dominating set ($k\geq 1$).
Therefore, for any graph $G$, we have $\gamma_{\times
k}\left(G\right)<\gamma_{\times(k+1)}\left(G\right)$ whenever
$\delta\left({G}\right)\geq k-1$. Then it turns out that for fixed $r$ and
$n$, and $2\leq k\leq\binom{n-r}{r}$, we have $\gamma_{\times
k}\left(n,r\right)<\gamma_{\times(k+1)}\left(n,r\right)$, i.e. $\gamma_{\times
k}\left(n,r\right)$ is strictly increasing with respect to $k$.

In addition, notice that there is not monotonicity for the $k$-tuple
domination number with respect to induced subgraphs. However, in the case of
Kneser graphs, if $2r\leq m<n$, $K({m,r})$ is an induced subgraph of
$K({n,r})$ and we will show that $\gamma_{\times
k}\left(m,r\right)\geq\gamma_{\times k}\left(n,r\right)$ for every $k\geq 2$
such that $k\leq\binom{m-r}{r}+1$. This is, for each fixed $k\geq 2$,
$\gamma_{\times k}\left(n,r\right)$ is decreasing with respect to $n$.

######  Theorem 12.

If $D$ is a $k$-tuple dominating set of $K({n,r})$ with $k\geq 2$, then $D$ is
a $k$-tuple dominating set of $K({n+1,r})$. In consequence, we have
$\gamma_{\times k}\left(n+1,r\right)\leq\gamma_{\times k}\left(n,r\right)$ for
every $n$.

###### Proof.

Let $D$ be a $k$-tuple dominating set of $K({n,r})$. In order to see that $D$
is a $k$-tuple dominating set of $K({n+1,r})$, it is enough to show that every
vertex $u$ of $K({n+1,r})$ containing the element $n+1$ satisfies

$|N_{n+1}[u]\cap D|\geq k,$

where $N_{t}[u]$ denotes the neighbourhood of the vertex $u$ in the graph
$K({t,r})$.

Let $\tilde{u}$ be a $(r-1)$-subset of $[n]$ and $u=\tilde{u}\cup\\{n+1\\}$.
Let us define, for $b\in[n]\setminus\tilde{u}$, $u_{b}=\tilde{u}\cup\\{b\\}$.
Note that if $b\in[n]\setminus\tilde{u}$, then

$|N_{n+1}[u]\cap D|=|\\{w\in D:|w\cap\tilde{u}|=0\\}|\geq|N_{n}(u_{b})\cap
D|\geq\begin{cases}k-1,&\text{if }u_{b}\in D\\\ k,&\text{if }u_{b}\notin
D\end{cases}.$

Therefore, if there exists $b\in[n]\setminus\tilde{u}$ such that $u_{b}\notin
D$, then $|N_{n+1}[u]\cap D|\geq k$.

Otherwise, consider $u_{b}$ for some $b\in[n]\setminus\tilde{u}$. We have
$u_{b}\in D$ and in consequence, $|N_{n}(u_{b})\cap D|\geq k-1$. Consider
$z\in N_{n}(u_{b})\cap D$, and let $x$ be an element from $z$. Now, consider
the vertex $u_{x}$. Note that $w\cap\tilde{u}=\emptyset$ for every $w\in
N_{n}(u_{x})\cap D$. Besides, $\tilde{u}\cap z=\emptyset$ since $z\in
N_{n}(u_{b})$. It follows

$|N_{n+1}[u]\cap D|=|\\{w\in D:|w\cap\tilde{u}|=0\\}|\geq|N_{n}(u_{x})\cap
D|+1\geq k.$

Therefore $D$ is a $k$-tuple dominating set of $K({n+1,r})$.

∎

From theorems 11 and 12 we have the following.

######  Corollary 13.

For $k\geq 2$, $\gamma_{\times k}\left(n,r\right)\geq k+r$. Moreover, if
$n<r(k+r)$, then $\gamma_{\times k}\left(n,r\right)\geq k+r+1$.

The remaining of this section is devoted to obtain $\gamma_{\times k}$-sets
for $k=\binom{n-r}{r}-t$ when $n$ is large enough with respect to both $r$ and
$t$. As we have mentioned, if $k=\binom{n-r}{r}+1$, the only $\gamma_{\times
k}$-set of $K({n,r})$ is the set of vertices itself. On the other hand, when
$n\geq 3r-1$, the diameter of the Kneser graph $K({n,r})$ is equal to $2$
[38]. In these cases, any pair of vertices in $K({n,r})$ are adjacent or they
have a common neighbour. Thus, for $k=\binom{n-r}{r}$ and $n\geq 3r-1$, it
follows that $\gamma_{\times k}\left(n,r\right)=\binom{n}{r}-1$. In a similar
way, we prove that for a positive integer $t$, when
$n\geq(t+3)r-\left\lceil\frac{t+2}{2}\right\rceil$, every set of $t+2$
vertices in $K({n,r})$ is contained in the closed neighborhood of some vertex
and in consequence, for $k=\binom{n-r}{r}-t$, it follows that $\gamma_{\times
k}\left(n,r\right)=\binom{n}{r}-(t+1)$.

######  Remark 14.

Let $t\in\mathbb{N}$, $t\geq 2$, and let $S$ be a set of $t$ vertices of
$K({n,r})$ such that each vertex $u\in S$ intersects at least one vertex in
$S\setminus\\{u\\}$. It holds

$\left|\bigcup_{v\in S}v\right|\leq tr-\left\lceil\frac{t}{2}\right\rceil$ (4)

######  Lemma 15.

Let $t\geq 2$. If $n\geq(t+1)r-\left\lceil\frac{t}{2}\right\rceil$ and $S$ is
a set of $t$ vertices of $K({n,r})$, then there exists a vertex $w$ of
$K({n,r})$ such that $S\subseteq N[w]$.

###### Proof.

Let $t,r,n\in\mathbb{N}$ such that $t\geq 2$ and
$n\geq(t+1)r-\left\lceil\frac{t}{2}\right\rceil$, and let $S$ be a set of $t$
vertices of $K({n,r})$. If there exists $w\in S$ such that $w\cap u=\emptyset$
for every $u\in S\setminus\\{w\\}$, the result holds. Now, assume that each
vertex of $S$ intersects at least another vertex in $S$. Thus, by Remark 14,
it follows (4). Since $n\geq(t+1)r-\left\lceil\frac{t}{2}\right\rceil$, we
have $\left|[n]\setminus\bigcup_{v\in S}v\right|=n-\left|\bigcup_{v\in
S}v\right|\geq r$ and there exists at least one vertex
$w\in[n]\setminus\bigcup_{v\in S}v$. Since $w\cap v=\emptyset$ for each $v\in
S$, we have $S\subseteq N[w]$, and the statement holds. ∎

######  Theorem 16.

For $t\in\mathbb{N}\cup\\{0\\}$,
$n\geq(t+3)r-\left\lceil\frac{t+2}{2}\right\rceil$ and $k=\binom{n-r}{r}-t$,
it holds $\gamma_{\times k}\left(n,r\right)=\binom{n}{r}-(t+1)$. Moreover, for
every set $S\subseteq V(K({n,r}))$ with cardinality $t+1$,
$V(K({n,r}))\setminus S$ is a $\gamma_{\times k}$-set.

###### Proof.

Let $S$ be a set of vertices of $K({n,r})$ with cardinality $t+2$. Let us show
that the set $D=V(K({n,r}))\setminus S$ is not a $k$-tuple dominating set. In
fact, by Lemma 15, we have that there exists a vertex $w\in V(K({n,r}))$ such
that $S\subseteq N[w]$. Thus, $|N[w]\cap
D|=|N[w]|-|S|=\binom{n-r}{r}+1-(t+2)=k-1$. In consequence,
$V(K({n,r}))\setminus S$ is not a $k$-tuple dominating set of $K({n,r})$.
Since it is true for any set of vertices $S$ with cardinality $t+2$, it
follows that $\gamma_{\times k}\left(n,r\right)\geq\binom{n}{r}-(t+1)$.

On the other hand, let $S$ be any set of vertices of $K({n,r})$ with
cardinality $t+1$, and $D=V(K({n,r}))\setminus S$. Let $u\in V(K({n,r}))$. We
have

$|N[u]\cap D|=|N[u]|-\underbrace{|N[u]\cap
S|}_{\leq|S|}\geq\binom{n-r}{r}+1-(t+1)=k$

Thus, $D$ is a $k$-tuple dominating set, and $\gamma_{\times
k}\left(n,r\right)\leq|D|=\binom{n}{r}-(t+1)$.

Therefore, $\gamma_{\times k}\left(n,r\right)=\binom{n}{r}-(t+1)$. ∎

######  Remark 17.

Note that if $n=(t+3)r-\left\lceil\frac{t+2}{2}\right\rceil-1$ and
$k=\binom{n-r}{r}-t$, then $\gamma_{\times
k}\left(n,r\right)<\binom{n}{r}-(t+1)$. In fact, we may consider the following
set $S$. For $t$ even,

$\displaystyle S=\bigg{\\{}$
$\displaystyle[\xi+1..\xi+r],[\xi+r..\xi+2r-1],\,\xi=(x-1)(2r-1),\text{ with
}x\in\left[\frac{t}{2}+1\right]\bigg{\\}}$

and for $t$ odd,

$\displaystyle S=\bigg{\\{}$
$\displaystyle[\xi+1..\xi+r],[\xi+r..\xi+2r-1],\,\xi=(x-1)(2r-1),\text{ with
}x\in\left[\left\lceil\frac{t}{2}\right\rceil+1\right]\bigg{\\}}\cup$
$\displaystyle\bigg{\\{}$
$\displaystyle[\xi+1..\xi+r],[\xi+r..\xi+2r-1],[\xi+2r..\xi+3r-2],\,\xi=\left\lceil\frac{t}{2}\right\rceil(2r-1)\bigg{\\}}.$

In both cases, $S$ is a set of $t+2$ vertices and $V(K({n,r}))\setminus S$ is
a $k$-tuple dominating set. Thus, $\gamma_{\times
k}\left(n,r\right)\leq\binom{n}{r}-(t+2)$.

##  4 $k$-tuple domination on Kneser graphs $K({n,2})$

The study of subsets of vertices satisfying certain restriction in Kneser
graphs $K({n,2})$ deserves a particular analysis, since this subclass of
Kneser graphs has a remarkable structure. For instance, in [5, 14, 16, 21, 27,
26] the authors studied the corresponding invariant in the subclass $K({n,2})$
separately. As we have mentioned, in [26] it is shown that $\gamma_{\times
1}\left(n,2\right)=3$ for every $n\geq 4$. In this section we focus on the
$k$-tuple domination number $\gamma_{\times k}\left(n,2\right)$ for $k\geq 2$.
To this end, let us see a characterization of the $k$-tuple dominating sets of
$K({n,2})$ in terms of the occurrences of the elements in $[n]$.

######  Lemma 18.

Let $n\geq 5$. $D$ is a $k$-tuple dominating set of $K({n,2})$ if and only if
for every pair $a,b\in[n]$

$i_{a}+i_{b}\leq\begin{cases}|D|-k+2,&\text{if }\\{a,b\\}\in D,\\\
|D|-k,&\text{if }\\{a,b\\}\notin D.\end{cases}$

###### Proof.

Let $D$ be a set of vertices of $K({n,2})$ and let $u=\\{a,b\\}$ be a vertex
of $K({n,2})$. The amount of vertices in $D$ that contain either the element
$a$ or $b$ is exactly $i_{a}+i_{b}-1$ when $u\in D$ and $i_{a}+i_{b}$
otherwise.

On the one hand, if $u\in D$, then we have

$\displaystyle|D\cap N\left[{u}\right]|$ $\displaystyle=|D|-|\\{v\in D:v\neq
u\wedge v\cap u\neq\emptyset\\}|=$ (5) $\displaystyle=|D|-\left(|\\{v\in
D:a\in v\vee b\in v\\}|-1\right)=$
$\displaystyle=|D|-(i_{a}+i_{b}-1)+1=|D|+2-(i_{a}+i_{b}).$

On the other hand, whether $u\notin D$ it holds that

$|D\cap N\left[{u}\right]|=|D|-|\\{v\in D:a\in v\vee b\in
v\\}|=|D|-(i_{a}+i_{b})=|D|-(i_{a}+i_{b}).$ (6)

From (5) and (6) it turns out that $D$ is a $k$-tuple dominating set if and
only if for every pair of elements $a,b\in[n]$ it holds

$\begin{cases}|D|+2-(i_{a}+i_{b})\geq k,&\text{if }\\{a,b\\}\in D,\\\
|D|-(i_{a}+i_{b})\geq k,&\text{if }\\{a,b\\}\notin D.\end{cases}$

Or, equivalently

$i_{a}+i_{b}\leq\begin{cases}|D|-k+2,&\text{if }\\{a,b\\}\in D,\\\
|D|-k,&\text{if }\\{a,b\\}\notin D.\end{cases}$

∎

######  Remark 19.

Note that if $D$ is a $k$-tuple dominating set and $\\{a,b\\}\in D$, then from
Lemma 18 together with the fact that $i_{b}\geq 1$, we have that for any
$a\in[n]$, it holds $i_{a}\leq|D|-k+1$.

From Theorem 11 with $r=2$, we have that $\gamma_{\times
k}\left(n,2\right)=k+2$ if and only if $n\geq 2(k+2)$. In addition, from
monotonicity, it follows that for $k\geq 2$ and $n<2(k+2)$, $\gamma_{\times
k}\left(n,2\right)\geq k+3$. Moreover, in the following result we state that
the only value of $n$ for which this bound is tight is $n=2k+3$. We introduce
the following notation. Given a set $A$ and a positive integer $r\leq|A|$, we
denote by $\binom{A}{r}$ the set of all the $r$-subsets of $A$.

######  Theorem 20.

If $k\geq 2$, then $\gamma_{\times k}\left(n,2\right)=k+3$ if and only if
$n=2k+3$.

###### Proof.

Let $k\geq 2$ and $n\leq 2k+3$. Let us suppose that there exists a $k$-tuple
dominating set $D=\\{u_{1},\ldots,u_{k+3}\\}$ of $K({n,2})$ with cardinality
$k+3$. We will prove that $n$ must be equal to $2k+3$. Note that it is enough
to prove that $n\geq 2k+3$. Let us consider a vertex $u$, and let $a\in u$. By
Remark 19 we have $i_{a}\leq 4$. Moreover, we can prove the following.

Claim. $i_{a}\leq 2$ for every $a\in[n]$.

_Proof._ Suppose, on the contrary, that $i_{a}\geq 3$ for some $a\in[n]$.

Note that there exists $b\in[n]-\\{a\\}$ such that $\\{a,b\\}\notin D$ and
$i_{b}\geq 1$. In fact, if for every element $x\neq a$ with $i_{x}\geq 1$ we
have $\\{a,x\\}\in D$, then there are at most $i_{a}+1$ elements in $[n]$ that
appear in vertices of $D$. Let $x$ be an element different from $a$ such that
$i_{x}\geq 1$. It turns out that $\\{a,x\\}\in D$ and by Lemma 18
$i_{a}+i_{x}\leq 5$.

Then if $i_{a}=4$, we have $i_{x}=1$ and $k+3=|D|=4$ which contradicts that
$k\geq 2$. On the other hand, if $i_{a}=3$ then it turns out that $i_{y}\leq
2$ for every $y\neq a$ with $i_{y}\geq 1$, and we have

$2(k+3)=2|D|=\sum_{y=1}^{n}i_{y}\leq i_{a}+2i_{a}=9.$

We also get $k+3=4$, which does not hold since $k\geq 2$.

Therefore, it is possible to choose $b\in[n]$ such that $i_{b}\geq 1$ and
$\\{a,b\\}\notin D$. Thus $i_{a}\geq 3$, $i_{b}\geq 1$, and in consequence
$i_{a}+i_{b}\geq 4$, which leads to a contradiction since by Lemma 18 we have
$i_{a}+i_{b}\leq 3$.

We conclude $i_{a}\leq 2$ for all $a\in[n]$. $(\square)$

Let $n_{1}=|X_{1}|$ and $n_{2}=|X_{2}|$. We have $n\geq n_{2}+n_{1}$ and
$2|D|=2n_{2}+n_{1}$. So

$n\geq n_{2}+n_{1}=2|D|-n_{2}=2(k+3)-n_{2}=2(k+2)+(2-n_{2}).$

Since $n<2(k+2)$, it turns out that $n_{2}\geq 3$. Let us see that $n_{2}$ is
exactly $3$.

Claim. $n_{2}=3$.

_Proof._ Suppose that $a$ and $b$ are two elements in $[n]$ such that
$i_{a}=i_{b}=2$, and let $v=\\{a,b\\}$. If $v\notin D$, by Lemma 18
$i_{a}+i_{b}\leq 3$ which leads to a contradiction. Thus, $v\in D$. If
$n_{2}\geq 4$, let us consider $a_{1},a_{2},a_{3},a_{4}$ such that
$i_{a_{j}}=2$ for $1\leq j\leq 4$. Then $\\{a_{1},a_{j}\\}\in D$ for every
$2\leq j\leq 4$, and $i_{a_{1}}\geq 3$ which contradicts the fact that
$i_{a_{1}}=2$. Thus, $n_{2}=3$. $(\square)$

Therefore we have $n\geq n_{2}+n_{1}=2k+3$. In consequence, it turns out that
if $\gamma_{\times k}\left(n,2\right)=k+3$, then $n=2k+3$.

On the other hand, if $n=2k+3$, then from Theorem 11 and monotonicity, we have
$\gamma_{\times k}\left(n,2\right)\geq k+3$. Now, let us see that there exists
a $k$-tuple dominating set $\widehat{D}$ with cardinality $k+3$. From the
reasoning above, we have that $\widehat{D}=X_{1}\cup X_{2}$, $|X_{2}|=3$ and
$\binom{X_{2}}{2}\subseteq\widehat{D}$. In fact, consider the set
$\widehat{D}$ given by

$\widehat{D}=\binom{[3]}{2}\cup\\{\\{2a,2a+1\\}:2\leq a\leq k+1\\}.$

$\widehat{D}$ is a $k$-tuple dominating set of $K({n,2})$ with
$|\widehat{D}|=k+3$. Therefore $\gamma_{\times k}\left(2k+3,2\right)=k+3$.

We conclude that for $k\geq 2$, $\gamma_{\times k}\left(n,2\right)=k+3$ if and
only if $n=2k+3$.

∎

As a by-product of the proof of Theorem 20 we have that if $n=2k+3$ with
$k\geq 2$, and $D$ is a $\gamma_{\times k}$-set of $K({n,2})$, then up to
automorphism

$D=\binom{[3]}{2}\cup\\{\\{2a,2a+1\\}:2\leq a\leq k+1\\}.$

Notice that in theorems 11 and 20, we provide $\gamma_{\times
k}\left(n,2\right)$ for $n\geq 2k+3$. From monotonicity on $n$ it follows that
if $n\leq 2k+2$, then $\gamma_{\times k}\left(n,2\right)\geq k+4$. Moreover,
in the remaining of this section we will obtain $\gamma_{\times
k}\left(n,2\right)$ if $n$ is large enough with respect to $k$. To this end we
give lower bounds for $\gamma_{\times k}\left(n,2\right)$, and afterwards we
prove that these bounds are tight by providing $k$-tuple dominating sets of
$K({n,2})$ with the desired cardinality.

######  Proposition 21.

Let $\alpha,n\in\mathbb{N}$ with $\alpha\geq 2$ and $n\geq
2\alpha+3+(\alpha\mod 2)$

  1. 1.

$\gamma_{\times k}\left(n,2\right)\geq k+2\alpha$, if $\frac{2}{\alpha}k+4\leq
n<\frac{2}{\alpha-1}k+3$;

  2. 2.

$\gamma_{\times k}\left(n,2\right)\geq k+2\alpha+1$, if
$n=\left\lceil\frac{2}{\alpha}k\right\rceil+3$.

###### Proof.

Let $\alpha,n\in\mathbb{N}$ with $\alpha\geq 2$ and $n\geq
2\alpha+3+(\alpha\mod 2)$. First, we prove the two following claims.

Claim. If $K({n,2})$ admits a $k$-tuple dominating set with cardinality
$k+2\alpha$, then $\alpha n\geq 2k+4\alpha$.

_Proof._ Let $D$ be a $k$-tuple dominating set of $K({n,2})$ with cardinality
$|D|=k+2\alpha$. Our goal is to prove that $\alpha n\geq 2(k+2\alpha)=2|D|$.
Let us suppose, on the contrary, that $\alpha n<2|D|$.

On the one side, by Lemma 18 for every pair of elements $a,b\in[n]$ we have

$i_{a}+i_{b}\leq\begin{cases}|D|-k+2=2(\alpha+1)&\text{if }\\{a,b\\}\in D,\\\
|D|-k=2\alpha&\text{if }\\{a,b\\}\notin D.\end{cases}$ (7)

Since $\alpha n<2|D|=\sum_{x\in[n]}i_{x}$, we have that there is at least one
element $a\in[n]$ for which $i_{a}\geq\alpha+1$. For every other element $b\in
X_{\alpha}^{\geq}$, it holds $i_{a}+i_{b}\geq 2\alpha+1$, and by (7)
$\\{a,b\\}\in D$.

If $|X_{\alpha}^{\geq}|>1$, then we have that for every $x\in
X_{\alpha}^{\geq}$, $i_{x}\leq\alpha+2$. In fact, if for some element $y$ it
holds $i_{y}>\alpha+2$, then by (7) for every other $x\in[n]$

$i_{x}\leq 2(\alpha+1)-i_{y}<2(\alpha+1)-(\alpha+2)=\alpha,$

and $y$ would be the only element in $X_{\alpha}^{\geq}$, but
$|X_{\alpha}^{\geq}|>1$.

Let us see that $|X_{\alpha}^{\geq}|>1$. Otherwise,
$X_{\alpha}^{\geq}=\\{a\\}$ with $i_{a}\geq\alpha+1$ and in consequence

$\displaystyle\alpha n<2|D|$
$\displaystyle=\sum_{x\in[n]}i_{x}=i_{a}+\sum_{x\in[n]\setminus\\{a\\}}\overbrace{i_{x}}^{\leq\alpha-1}\leq
i_{a}+(n-1)(\alpha-1)=i_{a}+\alpha n-n-\alpha+1.$

Then, $i_{a}>n+(\alpha-1)\geq n$, which cannot be true since $i_{x}\leq n-1$
for every element $x\in[n]$. Therefore, $|X_{\alpha}^{\geq}|>1$. In
consequence, $i_{x}\leq\alpha+2$ for every $x\in X_{\alpha}^{\geq}$. What is
more, if $y\in X_{\alpha+2}$, then for every $x\in X_{\alpha}^{\geq}$ we have
$i_{x}\leq 2(\alpha+1)-i_{y}=\alpha$ and it turns out that $i_{x}=\alpha$.
Then either $X_{\alpha}^{\geq}=X_{\alpha}\cup X_{\alpha+1}$ or
$X_{\alpha}^{\geq}=X_{\alpha}\cup X_{\alpha+2}$ with $|X_{\alpha+2}|=1$.

Case 1.

$X_{\alpha}^{\geq}=X_{\alpha}\cup X_{\alpha+1}$.

Since for $a\in X_{\alpha+1}$ and every $b\in X_{\alpha}^{\geq}$ we have
$\\{a,b\\}\in D$, then $|X_{\alpha}^{\geq}|\leq i_{a}+1=\alpha+2$, and we have

$\displaystyle 2|D|$ $\displaystyle=\sum_{x\in[n]}i_{x}=\sum_{x\in
X_{\alpha}^{\geq}}i_{x}+\sum_{x\in X_{\alpha-1}^{\leq}}i_{x}\leq$
$\displaystyle\leq|X_{\alpha}^{\geq}|(\alpha+1)+\underbrace{|X_{\alpha-1}^{\leq}|}_{n-|X_{\alpha}^{\geq}|}(\alpha-1)=$
$\displaystyle=n(\alpha-1)+2|X_{\alpha}^{\geq}|\leq n\alpha-n+2(\alpha+2).$

Since $2|D|\geq\alpha n+1$, it turns out that $n\leq 2(\alpha+2)-1$. By
hypothesis, we have

$n\geq\begin{cases}2(\alpha+2),&\text{if $\alpha$ is odd},\\\
2(\alpha+2)-1,&\text{if $\alpha$ is even}.\end{cases}$

Thus, $\alpha$ is even and $n=2(\alpha+2)-1$. Therefore

$\alpha n+1\leq 2|D|\leq n\alpha-n+2(\alpha+2)=\alpha n+1.$

It turns out that $2|D|=\alpha n+1$. But $2|D|$ is even whereas $\alpha n+1$
is odd.

Case 2.

$X_{\alpha}^{\geq}=X_{\alpha}\cup X_{\alpha+2}$ with $X_{\alpha+2}=\\{a\\}$.

Since for every $b\in X_{\alpha}$ we have $\\{a,b\\}\in D$, then
$|X_{\alpha}^{\geq}|\leq\alpha+3$, and we have

$\displaystyle 2|D|$ $\displaystyle=\sum_{x\in[n]}i_{x}=i_{a}+\sum_{x\in
X_{\alpha}}i_{x}+\sum_{x\in X_{\alpha-1}^{\leq}}i_{x}\leq$
$\displaystyle\leq(\alpha+2)+\underbrace{|X_{\alpha}|}_{|X_{\alpha}^{\geq}|-1}\alpha+\underbrace{|X_{\alpha-1}^{\leq}|}_{n-|X_{\alpha}^{\geq}|}(\alpha-1)=$
$\displaystyle=n(\alpha-1)+|X_{\alpha}^{\geq}|+2\leq n\alpha-n+\alpha+5.$

Since $2|D|>\alpha n$, it turns out that $n<\alpha+5$. By hypothesis, $n\geq
2\alpha+3$, then $2\alpha+3<\alpha+5$, that implies $\alpha<2$, which cannot
be true since $\alpha\geq 2$.

In both cases, we arise to a contradiction. Therefore, we can conclude that
$\alpha n\geq 2k+4\alpha$ as claimed. $(\square)$

Claim. If $K({n,2})$ admits a $k$-tuple dominating set with cardinality
$k+2\alpha-1$, then $(\alpha-1)n\geq 2k+3(\alpha-1)$.

_Proof._ Let $D$ be a $k$-tuple dominating set of $K({n,2})$ with cardinality
$|D|=k+2\alpha-1$. We are intended to prove that $(\alpha-1)n\geq
2k+3(\alpha-1)$ or equivalently $(\alpha-1)n+\alpha+1\geq 2|D|$. Let us
suppose, on the contrary, that $(\alpha-1)n+\alpha+1<2|D|$.

By Lemma 18 for every pair of elements $a,b\in[n]$ we have

$i_{a}+i_{b}\leq\begin{cases}|D|-k+2=2\alpha+1&\text{if }\\{a,b\\}\in D,\\\
|D|-k=2\alpha-1&\text{if }\\{a,b\\}\notin D.\end{cases}$ (8)

Since $(\alpha-1)n<2|D|=\sum_{x\in[n]}i_{x}$, we have that there is at least
one element $a\in[n]$ for which $i_{a}\geq\alpha$. For every other element
$b\in X_{\alpha}^{\geq}$, it holds $i_{a}+i_{b}\geq 2\alpha$, and by (8)
$\\{a,b\\}\in D$.

Let us see that $|X_{\alpha}^{\geq}|>1$. On the contrary,
$X_{\alpha}^{\geq}=\\{a\\}$ and

$\displaystyle(\alpha-1)n+\alpha+1<2|D|$
$\displaystyle=\sum_{x\in[n]}i_{x}=i_{a}+\sum_{x\neq
a}\underbrace{i_{x}}_{\leq\alpha-1}\leq i_{a}+(\alpha-1)n-(\alpha-1).$

Thus, $i_{a}>2\alpha$, which cannot be true since $i_{x}\leq 2\alpha$ for
every element $x\in[n]$ by Remark 19. Therefore, $|X_{\alpha}^{\geq}|\geq 2$.

Then, we have that for every $x\in X_{\alpha}^{\geq}$, $i_{x}\leq\alpha+1$. In
fact, if for some element $y$ it holds that $i_{y}>\alpha+1$, then by (8) for
every other $x\in[n]$

$i_{x}\leq 2\alpha+1-i_{y}<2\alpha+1-(\alpha+1)=\alpha,$

and $y$ would be the only element in $X_{\alpha}^{\geq}$, but
$|X_{\alpha}^{\geq}|>1$. Therefore, $i_{x}\leq\alpha+1$ for every $x\in
X_{\alpha}^{\geq}$. What is more, there is at most one element in
$X_{\alpha+1}$ since if $x,y\in X_{\alpha+1}$, then $i_{x}+i_{y}=2\alpha+2$
and this cannot be true by (8).

Therefore, either $X_{\alpha}^{\geq}=X_{\alpha}$ or
$X_{\alpha}^{\geq}=X_{\alpha}\cup X_{\alpha+1}$ with $|X_{\alpha+1}|=1$.

Case 1.

$X_{\alpha}^{\geq}=X_{\alpha}$.

For every pair $a,b\in X_{\alpha}$ we have $\\{a,b\\}\in D$ since
$i_{a}+i_{b}=2\alpha$ and it holds (8). Thus $\binom{X_{\alpha}}{2}\subseteq
D$ and we have $|X_{\alpha}|\leq\alpha+1$. Then

$\displaystyle 2|D|$ $\displaystyle=\sum_{x\in[n]}i_{x}=\sum_{x\in
X_{\alpha}}i_{x}+\sum_{x\in X_{\alpha-1}^{\leq}}i_{x}\leq$
$\displaystyle\leq|X_{\alpha}|\alpha+\underbrace{|X_{\alpha-1}^{\leq}|}_{n-|X_{\alpha}|}(\alpha-1)=$
$\displaystyle=n(\alpha-1)+|X_{\alpha}|\leq n(\alpha-1)+\alpha+1.$

But we have assumed that $2|D|>n(\alpha-1)+\alpha+1$.

Case 2.

$X_{\alpha}^{\geq}=X_{\alpha}\cup X_{\alpha+1}$ with $X_{\alpha+1}=\\{a\\}$.

For every other $b\in X_{\alpha-1}^{\geq}$ we have $i_{a}+i_{b}\geq 2\alpha$
thus $\\{a,b\\}\in D$ and in consequence $|X_{\alpha-1}^{\geq}|\leq\alpha+2$.
If $X=X_{\alpha-1}\cup X_{\alpha}$, we have

$\displaystyle 2|D|$ $\displaystyle=\sum_{x\in[n]}i_{x}=i_{a}+\sum_{x\in
X}i_{x}+\sum_{x\in X_{\alpha-2}^{\leq}}i_{x}\leq$
$\displaystyle\leq(\alpha+1)+\underbrace{|X|}_{|X_{\alpha-1}^{\geq}|-1}\alpha+\underbrace{|X_{\alpha-2}^{\leq}|}_{n-|X_{\alpha-1}^{\geq}|}(\alpha-2)=$
$\displaystyle=n(\alpha-2)+2|X_{\alpha-1}^{\geq}|+1\leq
n(\alpha-1)-n+2\alpha+5.$

Since $2|D|>(\alpha-1)n+\alpha+1$, it turns out that $n<\alpha+4$, but by
hypothesis $n\geq 2\alpha+3\geq\alpha+5$, since $\alpha\geq 2$.

In both cases, we arise to a contradiction. Therefore, we can conclude that
$(\alpha-1)n\geq 2k+3(\alpha-1)$ as claimed. $(\square)$

Assume that $n=\left\lceil\frac{2}{\alpha}k\right\rceil+3$. Suppose that
$K(n,2)$ admits a $k$-tuple dominating set with cardinality $k+2\alpha$. From
the first claim, it follows that $\alpha n\geq 2k+4\alpha$, or, equivalently,

$n\geq\frac{2}{\alpha}k+4,$

which does not hold. Thus, there does not exist any $k$-tuple dominating set
with $k+2\alpha$ vertices and

$\gamma_{\times k}\left(n,2\right)\geq k+2\alpha+1.$

Similarly, if $\frac{2}{\alpha}k+4\leq n<\frac{2}{\alpha-1}k+3$ and $K(n,2)$
admits a $k$-tuple dominating set with cardinality $k+2\alpha-1$, from the
second claim it follows that $(\alpha-1)n\geq 2k+3(\alpha-1)$, i.e.

$n\geq\frac{2}{\alpha-1}k+3,$

which is not true. Then, there does not exist any $k$-tuple dominating set
with $k+2\alpha-1$ vertices and

$\gamma_{\times k}\left(n,2\right)\geq k+2\alpha.$

∎

### Construction of $k$-tuple dominating sets for $K({n,2})$

In order to provide $k$-tuple dominating sets of $K({n,2})$ whose
cardinalities achieve the lower bounds for $\gamma_{\times k}\left(n,2\right)$
given in Proposition 21, let us introduce the following definition.

######  Definition 22.

Let $m\in\mathbb{N}$. For $i\in\mathbb{N}$, $i<\frac{m}{2}$, we define
$D_{i}^{[m]}$ as the set

$D_{i}^{[m]}=\big{\\{}\\{\xi,\xi+i\\}:\xi\in[m]\big{\\}},$

where the sums are taken modulo $m$. And for $\alpha\in\mathbb{N}$,
$\alpha\geq 2$, such that $m>\alpha$, let
$a=\left\lfloor\frac{\alpha}{2}\right\rfloor$. We define $D^{m,\alpha}$ as the
set given by

$D^{m,\alpha}=\left(\bigcup_{i=1}^{a}D_{i}^{[m]}\right)\cup\widehat{D},$

with

$\widehat{D}=\begin{cases}\left\\{\left\\{\xi,\xi+\left\lfloor\frac{m}{2}\right\rfloor\right\\},\xi\in\left[\left\lfloor\frac{m}{2}\right\rfloor\right]\right\\},&\text{if
$\alpha$ is odd,}\\\ \emptyset,&\text{if $\alpha$ is even.}\end{cases}$

######  Example 23.

  * •

Let $\alpha=3$, $m=6>\alpha$ and
$a=\left\lfloor\frac{\alpha}{2}\right\rfloor=1$. The set
$D^{m,\alpha}=D^{6,3}$ is given by

$D^{6,3}=D_{1}^{[6]}\cup\widehat{D},$

where

$\displaystyle D_{1}^{[6]}$
$\displaystyle=\big{\\{}\\{1,2\\},\\{2,3\\},\\{3,4\\},\\{4,5\\},\\{5,6\\},\\{6,1\\}\big{\\}},$
$\displaystyle\widehat{D}$
$\displaystyle=\big{\\{}\\{1,4\\},\\{2,5\\},\\{3,6\\}\big{\\}}.$

$D^{6,3}$ is a set of vertices of $K({n,2})$ for every $n\geq 6$ and the
occurrences of the elements in $[n]$ for the set $D^{6,3}$ are

$i_{x}=\begin{cases}3=\alpha,&\text{if }x\in[6],\\\
0,&\text{otherwise}.\end{cases}$

Figure 4: Set $D^{6,3}$ in the Kneser graph $K({6,2})$

  * •

Let $\alpha=4$, $m=14>\alpha$ and
$a=\left\lfloor\frac{\alpha}{2}\right\rfloor=2$. The set
$D^{m,\alpha}=D^{14,4}$ is given by

$D^{14,4}=D_{1}^{[14]}\cup D_{2}^{[14]},$

where

$\displaystyle D_{1}^{[14]}=\big{\\{}$
$\displaystyle\\{1,2\\},\\{2,3\\},\\{3,4\\},\\{4,5\\},\\{5,6\\},\\{6,7\\},\\{7,8\\},\\{8,9\\},$
$\displaystyle\\{9,10\\},\\{10,11\\},\\{11,12\\},\\{12,13\\},\\{13,14\\},\\{14,1\\}\big{\\}},$
$\displaystyle D_{2}^{[14]}=\big{\\{}$
$\displaystyle\\{1,3\\},\\{2,4\\},\\{3,5\\},\\{4,6\\},\\{5,7\\},\\{6,8\\},\\{7,9\\},\\{8,10\\},$
$\displaystyle\\{9,11\\},\\{10,12\\},\\{11,13\\},\\{12,14\\},\\{13,1\\},\\{14,2\\}\big{\\}}.$

$D^{14,4}$ is a set of vertices of $K({n,2})$ for every $n\geq 14$ and the
occurrences of the elements in $[n]$ for the set $D^{14,4}$ are

$i_{x}=\begin{cases}4=\alpha,&\text{if }x\in[14],\\\
0,&\text{otherwise}.\end{cases}$

  * •

Let $\alpha=3$, $m=11>\alpha$, and
$a=\left\lfloor\frac{\alpha}{2}\right\rfloor=1$. The set
$D^{m,\alpha}=D^{11,3}$ is given by

$D^{11,3}=D_{1}^{[11]}\cup\widehat{D},$

where

$\displaystyle D_{1}^{[11]}$
$\displaystyle=\big{\\{}\\{1,2\\},\\{2,3\\},\\{3,4\\},\\{4,5\\},\\{5,6\\},\\{6,7\\},\\{7,8\\},\\{8,9\\},\\{9,10\\},\\{10,11\\},\\{11,1\\}\big{\\}},$
$\displaystyle\widehat{D}$
$\displaystyle=\big{\\{}\\{1,6\\},\\{2,7\\},\\{3,8\\},\\{4,9\\},\\{5,10\\}\big{\\}}.$

$D^{11,3}$ is a set of vertices of $K({n,2})$ for every $n\geq 11$ and the
occurrences of the elements in $[n]$ for the set $D^{11,3}$ are

$i_{x}=\begin{cases}3=\alpha,&\text{if }x\in[10],\\\ 2=\alpha-1,&\text{if
}x=11,\\\ 0,&\text{otherwise}.\end{cases}$

Let us observe that $D^{m,\alpha}\subseteq\binom{[m]}{2}$. In consequence,
$D^{m,\alpha}$ is a set of vertices of $K({n,2})$ for every $n\geq m$, and any
element in $[m]$ has at most $\alpha$ occurrences in $D^{m,\alpha}$. In fact,
$m\geq\alpha+1>2a$, i.e., $a<\frac{m}{2}$. So, each element $x\in[m]$ appears
in exactly two vertices of $D_{i}^{[m]}$ for each $1\leq i\leq a$. Moreover,
for $i\neq j$, $D_{i}^{[m]}\cap D_{j}^{[m]}=\emptyset$ since $i+j\leq 2a<m$.
On the other hand, for $\alpha$ odd, a vertex in $\widehat{D}$ is not in
$D_{i}^{[m]}$ for any $i$. Furthermore, every element $x\in[m]$ appears in
exactly one vertex of $\widehat{D}$ if $m$ is even, and every element
$x\in[m-1]$ appears in exactly one vertex of $\widehat{D}$ if $m$ is odd.

Thus, for both $\alpha$ and $m$ odd we have

$i_{x}\left(D^{m,\alpha}\right)=\begin{cases}\alpha,&\text{if }x\in[m-1],\\\
\alpha-1=2a,&\text{if }x=m,\\\ 0,&\text{otherwise}.\end{cases}$ (9)

and if either $\alpha$ or $m$ are even, then

$i_{x}\left(D^{m,\alpha}\right)=\begin{cases}\alpha,&\text{if }x\in[m],\\\
0,&\text{otherwise}.\end{cases}$ (10)

In any case, we have

$\left|D^{m,\alpha}\right|=\frac{1}{2}\sum_{x\in[n]}i_{x}=\left\lfloor\frac{\alpha
m}{2}\right\rfloor.$ (11)

######  Lemma 24.

Let $\alpha,k\in\mathbb{N}$ with $\alpha\geq 2$ and $n\geq\alpha+2$. If
$n\geq\frac{2}{\alpha}k+4$, then there exists a $k$-tuple dominating set of
$K({n,2})$ with cardinality $k+2\alpha$.

###### Proof.

Due to Lemma 18 a set $D$ is a $k$-tuple dominating set if and only if it
verifies, for every pair of elements $x$ and $y$ in $[n]$

$i_{x}+i_{y}\leq\begin{cases}|D|-k+2=2\alpha+2,&\text{if }\\{x,y\\}\in D,\\\
|D|-k=2\alpha,&\text{if }\\{x,y\\}\notin D.\end{cases}$

Therefore, it is enough to find a set $D$ of vertices with cardinality
$k+2\alpha$ such that $i_{x}\leq\alpha$ for each $x\in[n]$. Let
$a=\left\lfloor\frac{\alpha}{2}\right\rfloor$. Since $n\geq\alpha+2>2a+1$, we
have $a<\left\lfloor\frac{n}{2}\right\rfloor$. Thus, let us consider the set
$D^{n,\alpha}$ as in Definition 22. Note that
$\left|D^{n,\alpha}\right|=\left\lfloor\frac{\alpha n}{2}\right\rfloor$ by
(11). Moreover, $|D^{n,\alpha}|\geq k+2\alpha$. In fact, as
$\frac{2}{\alpha}k+4\leq n$, we have $\alpha n\geq 2(k+2\alpha)$. If either
$\alpha$ or $n$ are even, then

$2|D^{n,\alpha}|=n\alpha\geq 2(k+2\alpha).$

On the other hand, if both $\alpha$ and $n$ are odd then

$2|D^{n,\alpha}|=n\alpha-1\geq 2(k+2\alpha)-1.$

As $2|D^{n,\alpha}|$ is an even integer and $2(k+2\alpha)-1$ is an odd
integer, it turns out that $2|D^{n,\alpha}|>2(k+2\alpha)-1$ and in consequence
$2|D^{n,\alpha}|\geq 2(k+2\alpha)$.

In any case, $|D^{n,\alpha}|\geq k+2\alpha$ as claimed.

Note that $i_{x}(D^{n,\alpha})\leq\alpha$ for every $x\in[n]$, by (9) and
(10). Thus, eliminating any $|D^{n,\alpha}|-(k+2\alpha)$ vertices from
$D^{n,\alpha}$ gives as a result a set of vertices $D$ with cardinality
$k+2\alpha$ such that $i_{x}(D)\leq i_{x}(D^{n,\alpha})\leq\alpha$ for every
$x\in[n]$. This is, a $k$-tuple dominating set with cardinality $k+2\alpha$.

Therefore, $K({n,2})$ admits a $k$-tuple dominating set with cardinality
$k+2\alpha$. ∎

######  Example 25.

  * •

Let $\alpha=3$, $n=11$ and $k=9$. We have $\frac{2}{\alpha}k+4\leq
n<\frac{2}{\alpha-1}k+3$. We are in the hypothesis of Proposition 24. Let us
consider the set $D^{11,3}$ given in Example 23. We have
$\left|D^{11,3}\right|=16>15=k+2\alpha$. Thus, by eliminating any vertex of
$D^{11,3}$ we get a $k$-tuple dominating set $D$ of $K({11,2})$ with
cardinality $k+2\alpha$.

  * •

Let $\alpha=4$, $n=14$ and $k=17$. We have $\frac{2}{\alpha}k+4\leq
n<\frac{2}{\alpha-1}k+3$. We are in the hypothesis of Proposition 24. Let us
consider the set $D^{14,4}$ given in Example 23. We have
$\left|D^{14,4}\right|=28>25=k+2\alpha$. Thus, by eliminating any three
vertices of $D^{14,4}$ we get a $k$-tuple dominating set $D$ of $K({14,2})$
with cardinality $k+2\alpha$.

######  Lemma 26.

Let $\alpha,k\in\mathbb{N}$ with $\alpha\geq 2$ and $n\geq 2\alpha+3$. If
$n=\left\lceil\frac{2}{\alpha}k\right\rceil+3$, then there exists a $k$-tuple
dominating set of $K({n,2})$ with cardinality $k+2\alpha+1$.

###### Proof.

Due to Lemma 18 a set $D$ is a $k$-tuple dominating set if and only if for
every pair of elements $x$ and $y$ in $[n]$ it holds

$i_{x}+i_{y}\leq\begin{cases}|D|-k+2=2\alpha+3&\text{if }\\{x,y\\}\in D,\\\
|D|-k=2\alpha+1&\text{if }\\{x,y\\}\notin D.\end{cases}$

Therefore it is enough to find a set $D$ of vertices with cardinality
$k+2\alpha+1$ such that $\alpha\leq i_{x}\leq\alpha+1$ for each $x\in[n]$, and
$\\{x,y\\}\in D$ for every pair $x,y\in X_{\alpha+1}$.

Let $\lambda\in\mathbb{N}$ such that $k=\alpha\lambda+b$ with $0\leq
b\leq\alpha-1$. And let $a=\left\lfloor\frac{\alpha}{2}\right\rfloor$. We will
give such a set $D$ in terms of $b$ considering the cases $b=0$, $1\leq b\leq
a$ and $a+1\leq b\leq\alpha-1$.

In order to do so, let us consider for $h\in\mathbb{N}$, $1\leq h<n-\alpha$
the set

$D(h)=D^{n-h,\alpha}\cup\binom{[n-h+1..n]}{2}.$ (12)

Let us note that if $(n-h)\alpha$ is even, then using (10) we have that each
element $x\in[n-h]$ has exactly $\alpha$ occurrences in $D^{n-h,\alpha}$ and
none in $\binom{[n-h+1..n]}{2}$, and each $x\in[n-h+1..n]$ has exactly $h-1$
occurrences in $\binom{[n-h+1..n]}{2}$ and none in $D^{n-h,\alpha}$. In
consequence

$i_{x}(D(h))=\begin{cases}\alpha,&\text{if }x\in[n-h],\\\ h-1,&\text{if
}x\in[n-h+1..n].\end{cases}$ (13)

Furthermore, by (11) we have

$\left|D(h)\right|=\left|D^{n-h,\alpha}\right|+\left|\binom{[n-h+1..n]}{2}\right|=\frac{(n-h)\alpha}{2}+\binom{h}{2}.$
(14)

In the first case, $b=0$, we will prove that for $h=\alpha+2$ the set $D(h)$
is itself a $k$-tuple dominating set with cardinality $k+2\alpha$. In the
remaining cases, we will consider the set $D(h)$ for $h=2b+2$ and
$h=2b-\alpha+2$ respectively and modify them with the aim of giving $k$-tuple
dominating sets of the desired cardinality.

Case 1.

$b=0$.

Let $h=\alpha+2$. Since $n\geq 2\alpha+3$, we have $n-h\geq\alpha+1>\alpha$.
So, we consider the set $D=D(h)$ as in (12). Note that
$n=\left\lceil\frac{2}{\alpha}k\right\rceil+3=2\lambda+3$. Thus, for $\alpha$
odd, we have both $n$ and $h$ are odd and in consequence $n-h$ is even. Thus,
$(n-h)\alpha$ is even. From (13) it turns out that $\alpha\leq
i_{x}\leq\alpha+1$ for each $x\in[n]$, and $\\{x,y\\}\in D$ for every pair
$x,y\in X_{\alpha+1}$. Thus, $D$ is a $k$-tuple dominating set. What is more,

$2|D|=\sum_{x\in[n]}i_{x}=(n-h)\alpha+h(\alpha+1)=\alpha
n+h=\alpha\left(\frac{2}{\alpha}k+3\right)+\alpha+2=2(k+2\alpha+1).$

Therefore, $|D|$ is a $k$-tuple dominating set with cardinality $k+2\alpha+1$.

Case 2.

$1\leq b\leq a$.

Let $h=2b+2$. $h$ is an even integer between $4$ and $2a+2\leq\alpha+2$. Since
$n\geq 2\alpha+3$, we have $n-h\geq(2\alpha+3)-(\alpha+2)=\alpha+1>\alpha$.
So, we consider the set $D(h)$ as in (12).

Note that $n=\left\lceil\frac{2}{\alpha}k\right\rceil+3=2\lambda+4$. Thus,
both $n$ and $h$ are even and in consequence also $n-h$. From (14),

$2|D(h)|=(n-h)\alpha+h(h-1)=(n\alpha+h)-h\underbrace{(\alpha-h+2)}_{\alpha-2b}=2(k+2\alpha+1)-\underbrace{h(\alpha-2b)}_{\geq
0},$ (15)

since

$2(k+2\alpha+1)=2k+4\alpha+2=2(\lambda\alpha+b)+4\alpha+2=(2\lambda+4)\alpha+(2b+2)=n\alpha+h.$

If $b<a$, let us consider the following set $D$.

$D=\Bigg{[}D(h)\setminus\underbrace{\Bigg{(}\smashoperator[r]{\bigcup_{\begin{subarray}{c}1\leq
j\leq b+1\\\ 1\leq\xi\leq\alpha-2b\end{subarray}}^{}}\
\big{\\{}\\{\xi,\xi+j\\}\big{\\}}\Bigg{)}}_{D_{1}}\Bigg{]}\cup\underbrace{\Bigg{(}\smashoperator[r]{\bigcup_{\begin{subarray}{c}1\leq
j\leq b+1\\\ 1\leq\xi\leq\alpha-2b\end{subarray}}^{}}\
\big{\\{}\\{\xi,n-h+2j-1\\},\\{\xi+j,n-h+2j\\}\big{\\}}\Bigg{)}}_{D_{2}},$

where the sums in $D_{1}$ are taken modulo $n-h$.

Let us see that $D_{1}\subseteq D(h)$. In fact, we have that $b+1\leq a$, so
for each $j$ it holds $\\{\xi,\xi+j\\}\in D_{j}^{[n-h]}\subseteq D(h)$. What
is more, $\alpha-2b<\alpha<n-h$, so for fixed $j$, the vertices
$\\{\xi,\xi+j\\}$ are different. In consequence, $|D_{1}|=(b+1)(\alpha-2b)$.

On the other hand, $D_{2}\cap D(h)=\emptyset$ since no vertex in $D(h)$ has an
element in $[n-h]$ and other in $[n-h+1..n]$. And the vertices in $D_{2}$ are
different. Thus, $|D_{2}|=2(b+1)(\alpha-2b)$.

Note that for each $x\in[n]$, we have

$i_{x}(D)=i_{x}(D(h))-i_{x}(D_{1})+i_{x}(D_{2}).$

For $x\in[n-h]$, we have $i_{x}(D_{1})=i_{x}(D_{2})$, and in consequence

$i_{x}(D)=i_{x}(D(h))=\alpha,$

and for $x\in[n-h+1..n]$, we have $i_{x}(D_{1})=0$ and
$i_{x}(D_{2})=\alpha-2b$, and in consequence

$i_{x}(D)=\underbrace{i_{x}(D(h))}_{h-1}+\alpha-2b=\alpha+1.$

We have $\alpha\leq i_{x}(D)\leq\alpha+1$ for each $x\in[n]$, and
$\\{x,y\\}\in D$ for every pair $x,y\in X_{\alpha+1}$. Thus, $D$ is a
$k$-tuple dominating set. Furthermore,

$|D|=|D(h)|-|D_{1}|+|D_{2}|=k+2\alpha+1.$

Therefore, $|D|$ is a $k$-tuple dominating set with cardinality $k+2\alpha+1$.

If $b=a$ and $\alpha$ is even then the set $D(h)$ is itself a $k$-tuple
dominating set with cardinality $k+2\alpha+1$ since (15) holds. If $\alpha$ is
odd, then let us consider the following set $D$.

$D=\Bigg{[}D(h)\setminus\underbrace{\Bigg{(}\smashoperator[r]{\bigcup_{{1\leq\xi\leq
b+1}}^{}}\
\big{\\{}\\{\xi,\xi+1\\}\big{\\}}\Bigg{)}}_{D_{1}}\Bigg{]}\cup\underbrace{\Bigg{(}\smashoperator[r]{\bigcup_{1\leq\xi\leq
b+1}^{}}\
\big{\\{}\\{\xi,n-h+2\xi-1\\},\\{\xi+1,n-h+2\xi\\}\big{\\}}\Bigg{)}}_{D_{2}}.$

Note that $D_{1}\subseteq D_{1}^{[n-h]}\subseteq D(h)$. Moreover, since
$\alpha$ is odd, we have $\alpha=2a+1=2b+1$. Thus,
$n-h\geq(2\alpha+3)-(2b+2)=\alpha+2>b+1$. So, the vertices in $D_{1}$ are
different and $|D_{1}|=b+1$. As in the case $b<a$, $D_{2}\cap D(h)=\emptyset$
and the vertices in $D_{2}$ are different. Thus, $|D_{2}|=2b+2$. We have that
for each $x\in[n]$ it holds

$i_{x}(D)=i_{x}(D(h))-i_{x}(D_{1})+i_{x}(D_{2}).$

We have $i_{x}(D_{1})=i_{x}(D_{2})$ if $x\in[n-h]$ and $i_{x}(D_{1})=0$,
$i_{x}(D_{2})=1$ if $x\in[n-h+1..n]$. In consequence

$i_{x}(D)=\begin{cases}\alpha,&\text{if }x\in[n-h],\\\ h=\alpha+1,&\text{if
}x\in[n-h+1..n].\end{cases}$

This is, $\alpha\leq i_{x}(D)\leq\alpha+1$ for each $x\in[n]$, and
$\\{x,y\\}\in D$ for every pair $x,y\in X_{\alpha+1}$. $D$ is a $k$-tuple
dominating set with cardinality

$|D|=|D(h)|-|D_{1}|+|D_{2}|=k+2\alpha+1.$

Case 3.

$a+1\leq b\leq\alpha-1$.

Let $h=2b-\alpha+2$. We have $3\leq h\leq\alpha$, and $h$ has the same parity
as $\alpha$, and $n-h\geq(2\alpha+3)-\alpha=\alpha+3>\alpha$. So, we consider
the set $D(h)$ as in (12).

Note that $n=\left\lceil\frac{2}{\alpha}k\right\rceil+3=2\lambda+5$. Besides,
if $\alpha$ is odd, then both $n$ and $h$ are odd and in consequence $n-h$ is
even. So, in any case, $(n-h)\alpha$ is even. From (14),

$2|D(h)|=(n-h)\alpha+h(h-1)=(n\alpha+h)-h\underbrace{(\alpha-h+2)}_{2\alpha-2b}=2(k+2\alpha+1)-\underbrace{2h(\alpha-b)}_{>0},$
(16)

since

$2(k+2\alpha+1)=2k+4\alpha+2=2(\lambda\alpha+b)+4\alpha+2=(2\lambda+5)\alpha+(2b-\alpha+2)=n\alpha+h.$

The procedure is similar than Case 2. This is, we eliminate $h(\alpha-b)$
vertices from $D(h)$ and add another $2h(\alpha-b)$ vertices in order to get a
$k$-tuple dominating set with cardinality $k+2\alpha+1$.

If $\alpha$ is even, let us consider the following set $D$.

$D=\Bigg{[}D(h)\setminus\underbrace{\Bigg{(}\smashoperator[r]{\bigcup_{\begin{subarray}{c}1\leq
j\leq b-a+1\\\ 1\leq\xi\leq 2\alpha-2b\end{subarray}}^{}}\
\big{\\{}\\{\xi,\xi+j\\}\big{\\}}\Bigg{)}}_{D_{1}}\Bigg{]}\cup\underbrace{\Bigg{(}\smashoperator[r]{\bigcup_{\begin{subarray}{c}1\leq
j\leq b-a+1\\\ 1\leq\xi\leq 2\alpha-2b\end{subarray}}^{}}\
\big{\\{}\\{\xi,n-h+2j-1\\},\\{\xi+j,n-h+2j\\}\big{\\}}\Bigg{)}}_{D_{2}},$

where the sums in $D_{1}$ are taken modulo $n-h$.

Let us see that $D_{1}\subseteq D(h)$. In fact, we have that
$b-a+1\leq\alpha-a=a$, so for each $j$ it holds $\\{\xi,\xi+j\\}\in
D_{j}^{[n-h]}\subseteq D(h)$. And, since $n\geq 2\alpha+3$ and
$h=2b-\alpha+2$, we have $n-h\geq 3\alpha-2b+1>2\alpha-2b$. So,
$2\alpha-2b<\alpha<n-h$, thus for fixed $j$, the vertices $\\{\xi,\xi+j\\}$
are different. In consequence, $|D_{1}|=(b-a+1)(2\alpha-2b)=h(\alpha-b)$.

On the other hand, $D_{2}\cap D(h)=\emptyset$ since no vertex in $D(h)$ has an
element in $[n-h]$ and other in $[n-h+1..n]$. Thus, the vertices in $D_{2}$
are different and it turns out that
$|D_{2}|=2(b-a+1)(2\alpha-2b)=2h(\alpha-b)$.

If $\alpha$ is odd, let us consider the set $D=\left[D(h)\setminus
D_{1}\right]\cup D_{2}$, where

$\displaystyle D_{1}=$
$\displaystyle\Bigg{(}\smashoperator[r]{\bigcup_{\begin{subarray}{c}1\leq
j\leq b-a\\\ 1\leq\xi\leq 2\alpha-2b\end{subarray}}^{}}\
\big{\\{}\\{\xi,\xi+j\\}\big{\\}}\Bigg{)}\cup\Bigg{(}\smashoperator[r]{\bigcup_{1\leq\xi\leq\alpha-b}^{}}\
\ \left\\{\left\\{\xi,\xi+\frac{n-h}{2}\right\\}\right\\}\Bigg{)},$
$\displaystyle D_{2}=$
$\displaystyle\Bigg{(}\smashoperator[r]{\bigcup_{\begin{subarray}{c}1\leq
j\leq b-a\\\ 1\leq\xi\leq 2\alpha-2b\end{subarray}}^{}}\
\big{\\{}\\{\xi,n-h+2j-1\\},\\{\xi+j,n-h+2j\\}\big{\\}}\Bigg{)}\ \cup$
$\displaystyle\Bigg{(}\smashoperator[r]{\bigcup_{1\leq\xi\leq\alpha-b}^{}}\ \
\left\\{\left\\{\xi,n\right\\},\left\\{\xi+\frac{n-h}{2},n\right\\}\right\\}\Bigg{)},$

and the sums in $D_{1}$ are taken modulo $n-h$.

Let us see that $D_{1}\subseteq D(h)$. In fact, we have that
$b-a\leq\alpha-1-a=a$, so for each $j$ it holds $\\{\xi,\xi+j\\}\in
D_{j}^{[n-h]}\subseteq D(h)$. And, since $n\geq 2\alpha+3$ and
$h=2b-\alpha+2$, we have $n-h\geq 3\alpha-2b+1>2\alpha-2b$. So,
$2\alpha-2b<\alpha<n-h$, thus for fixed $j$, the vertices $\\{\xi,\xi+j\\}$
are different. On the other hand, for $1\leq\xi\leq\alpha-b<\frac{n-h}{2}$, we
have $\left\\{\xi,\xi+\frac{n-h}{2}\right\\}\in\widehat{D}\subseteq D(h)$. In
consequence,

$|D_{1}|=(b-a)(2\alpha-2b)+(\alpha-b)=\underbrace{(2b-2a+1)}_{h}(\alpha-b)=h(\alpha-b).$

Besides, $D_{2}\cap D(h)=\emptyset$ since no vertex in $D(h)$ has an element
in $[n-h]$ and other in $[n-h+1..n]$. Thus, the vertices in $D_{2}$ are
different and it turns out that
$|D_{2}|=2(b-a)(2\alpha-2b)+2(\alpha-b)=2h(\alpha-b)$.

Either if $\alpha$ is even or odd, the set $D$ is a $k$-tuple dominating set
with cardinality $k+2\alpha+1$. In fact, note that for each $x\in[n]$ we have

$i_{x}(D)=i_{x}(D(h))-i_{x}(D_{1})+i_{x}(D_{2}).$

For $x\in[n-h]$, we have $i_{x}(D_{1})=i_{x}(D_{2})$, and in consequence

$i_{x}(D)=i_{x}(D(h))=\alpha.$

And for $x\in[n-h+1..n]$, we have $i_{x}(D_{1})=0$ and
$i_{x}(D_{2})=2\alpha-2b$, and in consequence

$i_{x}(D)=\underbrace{i_{x}(D(h))}_{h-1}+2\alpha-2b=\alpha+1.$

We have $\alpha\leq i_{x}(D)\leq\alpha+1$ for each $x\in[n]$, and
$\\{x,y\\}\in D$ for every pair $x,y\in X_{\alpha+1}$. Thus, $D$ is a
$k$-tuple dominating set. Furthermore,

$|D|=|D(h)|-|D_{1}|+|D_{2}|=k+2\alpha+1.$

Therefore, either if $\alpha$ is even or odd, we obtain a $k$-tuple dominating
set with cardinality $k+2\alpha+1$.

∎

######  Example 27.

  * •

Let $n=13$ and $k=15$. We have $n=\left\lceil\frac{2}{\alpha}k\right\rceil+3$
for $\alpha=3$, and $n\geq 9=2\alpha+3$. We are in the hypothesis of
Proposition 26. Thus, $K({13,2})$ admits a $k$-tuple dominating set with
cardinality $k+2\alpha+1=22$. Note that $k\equiv 0$ modulo $\alpha$, so it is
enough to consider the set

$D=D^{8,3}\cup\binom{[9..13]}{2}.$

  * •

Let $n=18$ and $k=29$. We have $n=\left\lceil\frac{2}{\alpha}k\right\rceil+3$
for $\alpha=4$, and $n\geq 11=2\alpha+3$. We are in the hypothesis of
Proposition 26. Thus, $K({18,2})$ admits a $k$-tuple dominating set with
cardinality $k+2\alpha+1=38$. Note that $k\equiv 1$ modulo $\alpha$, so let us
consider the set

$D^{*}=D^{14,4}\cup\binom{[15..18]}{2},$

with $D^{14,4}$ as in example 23. We obtain a $k$-tuple dominating set of
$K({18,2})$ deleting from $D^{*}$ the vertices

$\\{1,2\\},\\{2,3\\},\\{1,3\\},\\{2,4\\}$

and adding the vertices

$\\{1,15\\},\\{2,16\\},\\{2,15\\},\\{3,16\\},\\{1,17\\},\\{3,18\\},\\{2,17\\},\\{4,18\\}.$

Combining Proposition 21 with lemmas 24 and 26 yields the following result.

######  Theorem 28 (A).

Let $\alpha,n\in\mathbb{N}$ with $\alpha\geq 2$ and $n\geq
2\alpha+3+(\alpha\mod 2)$. We have

  1. 1.

$\gamma_{\times k}\left(n,2\right)=k+2\alpha$, if $\frac{2}{\alpha}k+4\leq
n<\frac{2}{\alpha-1}k+3$,

  2. 2.

$\gamma_{\times k}\left(n,2\right)=k+2\alpha+1$, if
$n=\left\lceil\frac{2}{\alpha}k\right\rceil+3$.

Let us see two remarks about the statement of Theorem 28 (A).

Firstly, observe that $\alpha=\left\lceil\frac{2k}{n-3}\right\rceil$ if and
only if $\frac{2}{\alpha}k+3\leq n<\frac{2}{\alpha-1}k+3$. Thus, if
$\alpha=\left\lceil\frac{2k}{n-3}\right\rceil$, then either
$\frac{2}{\alpha}k+4\leq n<\frac{2}{\alpha-1}k+3$, or $\frac{2}{\alpha}k+3\leq
n<\frac{2}{\alpha}k+4$ (i.e. $n=\left\lceil\frac{2}{\alpha}k\right\rceil$+3).

Secondly, consider $k,n\in\mathbb{N}$ with $n\geq 7$ and $\frac{n-3}{2}<k\leq
a\,\frac{n-3}{4}$ with $a=n-4$ if $n$ is even and $a=n-6+(n\mod 4)$ if $n$ is
odd, and $\alpha=\left\lceil\frac{2k}{n-3}\right\rceil$. Let us see that
$\alpha\geq 2$ and $n\geq 2\alpha+3+(\alpha\mod 2)$. The first inequality
arises from the fact that $k>\frac{n-3}{2}$. In consequence
$\alpha=\left\lceil\frac{2k}{n-3}\right\rceil\geq 2$. On the other hand, we
have $k\leq a\,\frac{n-3}{4}$, which leads us to
$\frac{2k}{n-3}\leq\frac{a}{2}$. Whether $n$ is even or odd, $a$ turns out to
be even. Thus, $\frac{a}{2}\in\mathbb{N}$ and
$\alpha=\left\lceil\frac{2k}{n-3}\right\rceil\leq\frac{a}{2}$, or equivalently
$2\alpha\leq a$. If $n$ is even, $a=n-4$, and it holds $n\geq 2\alpha+4$. If
$n$ is odd, then $a=n-6+(n\mod 4)$, and it holds $n\geq 2\alpha+5$ if $n\equiv
1\mod 4$, and $n\geq 2\alpha+3$ if $n\equiv 3\mod 4$. Moreover, if $\alpha$ is
odd and $n\equiv 3\mod 4$, then $\frac{a}{2}=\frac{n-3}{2}$ is even. Thus,
$\alpha\leq\frac{a}{2}-1$, and we have $n\geq 2\alpha+5$. In any case, $n\geq
2\alpha+3+(\alpha\mod 2)$ as claimed.

Thus, Theorem 28 (A) can be restated as follows.

######  Theorem 29 (B).

Let $k,n\in\mathbb{N}$ with $n\geq 7$ and $\frac{n-3}{2}<k\leq
a\,\frac{n-3}{4}$ where $a=n-4$ if $n$ is even and $a=n-6+(n\mod 4)$ if $n$ is
odd. Let $\alpha=\left\lceil\frac{2k}{n-3}\right\rceil$. It holds

  1. 1.

$\gamma_{\times k}\left(n,2\right)=k+2\alpha$, if $\frac{2}{\alpha}k+4\leq
n<\frac{2}{\alpha-1}k+3$;

  2. 2.

$\gamma_{\times k}\left(n,2\right)=k+2\alpha+1$, if
$n=\left\lceil\frac{2}{\alpha}k\right\rceil+3$.

It is worth noting that whereas in Theorem 29 (B) the values of
$\gamma_{\times k}\left(n,2\right)$ are computed for $\frac{n-3}{2}<k\leq
a\,\frac{n-3}{4}$, with $a=n-4$ if $n$ is even and $a=n-6+(n\mod 4)$ if $n$ is
odd, theorems 11 and 20 provide the values of $\gamma_{\times
k}\left(n,2\right)$ for $k\leq\frac{n-3}{2}$. In consequence, we have
determined $\gamma_{\times k}\left(n,2\right)$ for all $2\leq k\leq
a\,\frac{n-3}{4}$.

##  5 Discussion

Regarding $\gamma_{\times k}$-sets of $K({n,2})$ for large values of $k$,
recall that for $k=\binom{n-2}{2}+1$, we have $\gamma_{\times
k}\left(n,2\right)=\binom{n}{2}$, whereas for $k=\binom{n-2}{2}$,
$\gamma_{\times k}\left(n,2\right)=\binom{n}{2}-1$. Together with Theorem 16
for $r=2$, we have the following.

######  Corollary 30.

For $t\in\mathbb{N}$, if $k=\binom{n-2}{2}-t$ and $n\geq
2(t+3)-\left\lceil\frac{t+2}{2}\right\rceil$, then $\gamma_{\times
k}\left(n,2\right)=k+2n-4$.

Besides, in order to complete the study of $\gamma_{\times k}$-sets of
$K({n,2})$ for large values of $k$, we have also studied properties of the
$\gamma_{\times k}$-sets of $K({n,2})$ for
$k\in\left\\{\binom{n-4}{2}+2,\binom{n-3}{2}+1\right\\}$. In fact, we obtain
the following result. We omit the proof here for the sake of readability (it
can be found in [12]).

######  Proposition 31.

  * •

If $k=\binom{n-4}{2}+2$ and $6\leq n\leq 10$, then $\gamma_{\times
k}\left(n,2\right)=\binom{n-2}{2}+1$. Moreover,
$D=\binom{[n-2]}{2}\cup\big{\\{}\\{n-1,n\\}\big{\\}}$ is a $\gamma_{\times
k}$-set.

  * •

If $k=\binom{n-3}{2}+1$ and $n\geq 5$, then $\gamma_{\times
k}\left(n,2\right)=\binom{n-1}{2}$. Moreover, $D=\binom{[n-1]}{2}$ is a
$\gamma_{\times k}$-set.

Notice that although the set
$\binom{[n-2]}{2}\cup\big{\\{}\\{n-1,n\\}\big{\\}}$ given in the first item of
Proposition 31 is a $k$-tuple dominating set of $K({n,2})$ for every $n\geq
6$, it is not true that it is a $\gamma_{\times k}$-set for every $n$. For
instance, for $n=11$ and $k=23$ the set

$D=\binom{[6]}{2}\cup\binom{[7..11]}{2}\cup\tilde{D},$

where

$\tilde{D}=\big{\\{}\\{1,7\\},\\{2,7\\},\\{2,8\\},\\{3,8\\},\\{3,9\\},\\{4,9\\},\\{4,10\\},\\{5,10\\},\\{5,11\\}\big{\\}},$

is a $k$-tuple dominating set with cardinality
$\binom{n-2}{2}=\binom{9}{2}=36$.

With the aim of summarizing the results in this paper for $K({n,2})$, in
Appendix B we give a table that contains several values for $\gamma_{\times
k}\left(n,2\right)$. Some of these values are obtained taking into account
Lemma 18, Theorem 12, and upper bounds obtained by Integer Linear Programming.
In this regard, we consider the following ILP formulation for the $k$-tuple
dominating problem. The set of variables is given by $\\{x_{u},u\in V\\}$,
where

$x_{u}=\begin{cases}1,&\text{if }u\in D,\\\ 0,&\text{otherwise,}\end{cases}$

and the ILP model is formulated as

min $\displaystyle\sum_{u\in V}x_{u}$ (17) s/t $\displaystyle\sum_{u\in
N\left[{v}\right]}x_{u}\geq k,$ $\displaystyle\forall\,v\in V,$ $\displaystyle
x_{v}\in\\{0,1\\},$ $\displaystyle\forall\,v\in V.$

We implemented it in CPLEX solver [25] to obtain $k$-tuple dominating sets
that allowed us to determine an upper bound of $\gamma_{\times
k}\left(n,2\right)$ for certain values of $n$ and $k$, which together with the
lower bounds obtained using Lemma 18 and Theorem 12, were tight. Notice that
we have determined $\gamma_{\times k}\left(n,2\right)$ for every $n$ and
$k\leq 18$. For the general case, fixed $k$, the amount of values of $n$ for
which $\gamma_{\times k}\left(n,2\right)$ remains unknown is
$\Theta(\sqrt{k})$. However, for some of them we have upper bounds arising
from solving the ILP.

##  Appendix A $\gamma_{\times k}$-sets of the odd graph $K({11,5})$

Consider the Kneser graph $K({11,5})$. We will see that for any $k\in[7]$, we
have

$\gamma_{\times k}\left(11,5\right)=k\rho\left(11,5\right)=66k.$ (18)

For $k=1$, an minimum dominating set is also a maximum $2$-packing, which is
given by a Steiner System $S(4,5,11)$.

We obtain a Steiner system $S=S(4,5,11)$ with base set $[n]$ following the
construction given in [18]. Let us consider two sets $A=\\{1,2,3,4,5\\}$,
$B=\\{6,7,8,9,10,11\\}$. Suppose that $A$ is itself a block, and consider the
following scheme.

1 | (6,7) | (8,9) | (10,11)
---|---|---|---
2 | (6,8) | (9,10) | (7,11)
3 | (6,9) | (7,10) | (8,11)
4 | (6,10) | (7,8) | (9,11)
5 | (6,11) | (8,10) | (7,9)

In the set $S$ there are $30$ blocks of the form $aaabb$, $20$ blocks of the
form $aabbb$, $15$ of the form $abbbb$, and one block $aaaaa$, where $a$
denotes an element in $A$ and $b$ denotes an element in $B$. Notice that in
each row of the scheme there is an element $a\in A$ and three disjoint pairs
of elements of $B$. We form three blocks from each row taking the element $a$
and two of the three pairs. Doing so, we get the $15$ blocks of the form
$abbbb$. Now, for any three elements $bbb$ of $B$, taking into account that
any four elements are contained in exactly one block of $S$, there are exactly
two elements of $A$ for which $aabbb$ is a block. For instance, for
$\\{6,7,8\\}$, we have that $\\{1,6,7,8,9\\}$, $\\{2,6,7,8,11\\}$ and
$\\{4,6,7,8,10\\}$ are blocks in $S$ of the form $abbbb$. Thus, the block in
$S$ of the form $aabbb$ containing $\\{6,7,8\\}$ is $\\{3,5,6,7,8\\}$.
Finally, for any two elements $bb$ of $B$, with a similar reasoning we get two
blocks of the form $aaabb$. For example, for the set $\\{6,7\\}$ we have
$\\{3,5,6,7,8\\}$, $\\{2,4,6,7,9\\}$, $\\{2,5,6,7,10\\}$ and
$\\{3,4,6,7,11\\}$ are blocks of the form $aabbb$ which are in $S$. Thus, the
blocks in $S$ of the form $aaabb$ containing the pair $\\{6,7\\}$ are
$\\{1,2,3,6,7\\}$ and $\\{1,4,5,6,7\\}$.

With this procedure, we get a Steiner system $S(4,5,11)$. $S$ turns out to be
a $\gamma_{\times 1}$-set of the Kneser graph $K({11,5})$ as well as an
maximum $2$-packing.

For $k=2$, we obtain a $\gamma_{\times 2}$-set of $K({11,5})$ by taking
$S_{1}\cup S_{2}$ where $S_{1}$ and $S_{2}$ and two disjoint Steiner systems
$S(4,5,11)$. It is enough to consider the construction above with the
following schemes.

Scheme for $S_{1}$

1 | (6,7) | (8,9) | (10,11)
---|---|---|---
2 | (6,8) | (9,10) | (7,11)
3 | (6,9) | (7,10) | (8,11)
4 | (6,10) | (7,8) | (9,11)
5 | (6,11) | (8,10) | (7,9)

Scheme for $S_{2}$

6 | (1,5) | (2,4) | (3,7)
---|---|---|---
8 | (1,2) | (3,5) | (4,7)
9 | (1,4) | (2,3) | (5,7)
10 | (1,3) | (2,7) | (4,5)
11 | (1,7) | (2,5) | (3,4)

For $k=3$, we found a $k$-tuple dominating set $D$ with cardinality
$198=3\cdot 66$. Below, we list the vertices in $D$.

{1, 2, 3, 4, 5}

{1, 2, 3, 4, 7}

{1, 2, 3, 4, 8}

{1, 2, 3, 5, 9}

{1, 2, 3, 5, 11}

{1, 2, 3, 6, 7}

{1, 2, 3, 6, 8}

{1, 2, 3, 6, 11}

{1, 2, 3, 7, 10}

{1, 2, 3, 8, 9}

{1, 2, 3, 9, 10}

{1, 2, 3, 10, 11}

{1, 2, 4, 5, 6}

{1, 2, 4, 5, 9}

{1, 2, 4, 6, 8}

{1, 2, 4, 6, 10}

{1, 2, 4, 7, 9}

{1, 2, 4, 7, 11}

{1, 2, 4, 8, 10}

{1, 2, 4, 9, 11}

{1, 2, 4, 10, 11}

{1, 2, 5, 6, 8}

{1, 2, 5, 6, 10}

{1, 2, 5, 7, 8}

{1, 2, 5, 7, 9}

{1, 2, 5, 7, 10}

{1, 2, 5, 8, 11}

{1, 2, 5, 10, 11}

{1, 2, 6, 7, 9}

{1, 2, 6, 7, 11}

{1, 2, 6, 9, 10}

{1, 2, 6, 9, 11}

{1, 2, 7, 8, 10}

{1, 2, 7, 8, 11}

{1, 2, 8, 9, 10}

{1, 2, 8, 9, 11}

{1, 3, 4, 5, 6}

{1, 3, 4, 5, 10}

{1, 3, 4, 6, 7}

{1, 3, 4, 6, 9}

{1, 3, 4, 7, 11}

{1, 3, 4, 8, 9}

{1, 3, 4, 8, 10}

{1, 3, 4, 9, 11}

{1, 3, 4, 10, 11}

{1, 3, 5, 6, 7}

{1, 3, 5, 6, 10}

{1, 3, 5, 7, 8}

{1, 3, 5, 7, 9}

{1, 3, 5, 8, 10}

{1, 3, 5, 8, 11}

{1, 3, 5, 9, 11}

{1, 3, 6, 8, 9}

{1, 3, 6, 8, 11}

{1, 3, 6, 9, 10}

{1, 3, 6, 10, 11}

{1, 3, 7, 8, 10}

{1, 3, 7, 8, 11}

{1, 3, 7, 9, 10}

{1, 3, 7, 9, 11}

{1, 4, 5, 6, 11}

{1, 4, 5, 7, 8}

{1, 4, 5, 7, 10}

{1, 4, 5, 7, 11}

{1, 4, 5, 8, 9}

{1, 4, 5, 8, 11}

{1, 4, 5, 9, 10}

{1, 4, 6, 7, 8}

{1, 4, 6, 7, 10}

{1, 4, 6, 8, 11}

{1, 4, 6, 9, 10}

{1, 4, 6, 9, 11}

{1, 4, 7, 8, 9}

{1, 4, 7, 9, 10}

{1, 4, 8, 10, 11}

{1, 5, 6, 7, 9}

{1, 5, 6, 7, 11}

{1, 5, 6, 8, 9}

{1, 5, 6, 8, 10}

{1, 5, 6, 9, 11}

{1, 5, 7, 10, 11}

{1, 5, 8, 9, 10}

{1, 5, 9, 10, 11}

{1, 6, 7, 8, 9}

{1, 6, 7, 8, 10}

{1, 6, 7, 10, 11}

{1, 6, 8, 10, 11}

{1, 7, 8, 9, 11}

{1, 7, 9, 10, 11}

{1, 8, 9, 10, 11}

{2, 3, 4, 5, 7}

{2, 3, 4, 5, 8}

{2, 3, 4, 6, 9}

{2, 3, 4, 6, 10}

{2, 3, 4, 6, 11}

{2, 3, 4, 7, 10}

{2, 3, 4, 8, 11}

{2, 3, 4, 9, 10}

{2, 3, 4, 9, 11}

{2, 3, 5, 6, 9}

{2, 3, 5, 6, 10}

{2, 3, 5, 6, 11}

{2, 3, 5, 7, 10}

{2, 3, 5, 7, 11}

{2, 3, 5, 8, 9}

{2, 3, 5, 8, 10}

{2, 3, 6, 7, 8}

{2, 3, 6, 7, 9}

{2, 3, 6, 8, 10}

{2, 3, 7, 8, 9}

{2, 3, 7, 8, 11}

{2, 3, 7, 9, 11}

{2, 3, 8, 10, 11}

{2, 3, 9, 10, 11}

{2, 4, 5, 6, 7}

{2, 4, 5, 6, 11}

{2, 4, 5, 7, 8}

{2, 4, 5, 8, 10}

{2, 4, 5, 9, 10}

{2, 4, 5, 9, 11}

{2, 4, 5, 10, 11}

{2, 4, 6, 7, 9}

{2, 4, 6, 7, 10}

{2, 4, 6, 8, 9}

{2, 4, 6, 8, 11}

{2, 4, 7, 8, 9}

{2, 4, 7, 8, 11}

{2, 4, 7, 10, 11}

{2, 4, 8, 9, 10}

{2, 5, 6, 7, 8}

{2, 5, 6, 7, 11}

{2, 5, 6, 8, 9}

{2, 5, 6, 9, 10}

{2, 5, 7, 9, 10}

{2, 5, 7, 9, 11}

{2, 5, 8, 9, 11}

{2, 5, 8, 10, 11}

{2, 6, 7, 8, 10}

{2, 6, 7, 10, 11}

{2, 6, 8, 9, 11}

{2, 6, 8, 10, 11}

{2, 6, 9, 10, 11}

{2, 7, 8, 9, 10}

{2, 7, 9, 10, 11}

{3, 4, 5, 6, 8}

{3, 4, 5, 6, 9}

{3, 4, 5, 7, 9}

{3, 4, 5, 7, 11}

{3, 4, 5, 8, 11}

{3, 4, 5, 9, 10}

{3, 4, 5, 10, 11}

{3, 4, 6, 7, 8}

{3, 4, 6, 7, 11}

{3, 4, 6, 8, 10}

{3, 4, 6, 10, 11}

{3, 4, 7, 8, 9}

{3, 4, 7, 8, 10}

{3, 4, 7, 9, 10}

{3, 4, 8, 9, 11}

{3, 5, 6, 7, 8}

{3, 5, 6, 7, 10}

{3, 5, 6, 8, 11}

{3, 5, 6, 9, 11}

{3, 5, 7, 8, 9}

{3, 5, 7, 10, 11}

{3, 5, 8, 9, 10}

{3, 5, 9, 10, 11}

{3, 6, 7, 9, 10}

{3, 6, 7, 9, 11}

{3, 6, 7, 10, 11}

{3, 6, 8, 9, 10}

{3, 6, 8, 9, 11}

{3, 7, 8, 10, 11}

{3, 8, 9, 10, 11}

{4, 5, 6, 7, 9}

{4, 5, 6, 7, 10}

{4, 5, 6, 8, 9}

{4, 5, 6, 8, 10}

{4, 5, 6, 10, 11}

{4, 5, 7, 8, 10}

{4, 5, 7, 9, 11}

{4, 5, 8, 9, 11}

{4, 6, 7, 8, 11}

{4, 6, 7, 9, 11}

{4, 6, 8, 9, 10}

{4, 6, 9, 10, 11}

{4, 7, 8, 10, 11}

{4, 7, 9, 10, 11}

{4, 8, 9, 10, 11}

{5, 6, 7, 8, 11}

{5, 6, 7, 9, 10}

{5, 6, 8, 10, 11}

{5, 6, 9, 10, 11}

{5, 7, 8, 9, 10}

{5, 7, 8, 9, 11}

{5, 7, 8, 10, 11}

{6, 7, 8, 9, 10}

{6, 7, 8, 9, 11}

For $k\in\\{1,2,3\\}$ we gave a $\gamma_{\times k}$-set $D_{k}$ with
cardinality $66k$. By Remark 7, we have that $D_{7-k}=V\setminus D_{k}$ is a
$(7-k)$-tuple dominating set with cardinality $|D_{7-k}|=|V|-66k=66(7-k)$.
Finally, the set $D_{7}=V$ is a $\gamma_{\times 7}$-set with cardinality
$66\cdot 7$. Thus, (18) holds for every $k\in[7]$.

##  Appendix B Table for $\gamma_{\times k}\left(n,2\right)$

Table 1 shows the values of $\gamma_{\times k}\left(n,2\right)$ stated by the
results in this paper. Rows correspond to values of $k$ while columns
correspond to values of $n$. The superscript in each entry of the table
indicates from which result it follows, and the bounds arise from $k$-tuple
dominating sets obtained using CPLEX solver for (17) and monotonicity.

  1. ($a$)

Domination number [26].

  2. ($b$)

Theorem 29 (B).1.

  3. ($c$)

Theorem 29 (B).2.

  4. ($d$)

Corollary 30.

  5. ($e$)

Proposition 31.

  6. ($f$)

Lower bound from Lemma 18 and upper bound from $\gamma_{\times k}$-sets found
by ILP (17).

  7. ($g$)

Lower bound from Monotonicity (Theorem 12) and upper bound from
$\gamma_{\times k}$-sets found by ILP (17).

Table 1: $\gamma_{\times k}\left(n,2\right)$ for some values of $n$ and $k$.

## References

  * [1] Barrau, J. On the combinatory problem of Steiner.  Koninklijke Nederlandse Akademie van Wetenschappen Proceedings Series B Physical Sciences 11 (1908), 352–360.
  * [2] Bedo, M., Leite, J. V., Oliveira, R. A., and Protti, F. Geodetic convexity and Kneser graphs.  Applied Mathematics and Computation 449 (2023), 127964.
  * [3] Biggs, N. Some odd graph theory.  Annals of the New York Academy of Sciences 319, 1 (1979), 71–81.
  * [4] Bozovic, D., Kelenc, A., Peterin, I., and González Yero, I. Incidence dimension and $2$-packing number in graphs.  RAIRO - Operations Research 56, 1 (2022), 199–211.
  * [5] Brešar, B., Kos, T., and Torres, P. D. Grundy domination and zero forcing in Kneser graphs.  ARS MATHEMATICA CONTEMPORANEA 17 (2019), 419–430.
  * [6] Brešar, B., Cornet, M. G., Dravec, T., and Henning, M. A. $k$-domination invariants on Kneser graphs.  arXiv e-prints (2023), arxiv:2312.15464.
  * [7] Cabrera Martínez, A. A note on the $k$-tuple domination number of graphs.  ARS MATHEMATICA CONTEMPORANEA 5 (2022).
  * [8] Castro, A., Klavžar, S., Mollard, M., and Rho, Y. On the domination number and the $2$-packing number of Fibonacci cubes and Lucas cubes.  Computers & Mathematics with Applications 61, 9 (2011), 2655–2660.
  * [9] Chang, G. J. The upper bound on $k$-tuple domination numbers of graphs.  European Journal of Combinatorics 29, 5 (2008), 1333–1336.
  * [10] Clarke, N. E., and Gallant, R. P. On $2$-limited packings of complete grid graphs.  Discrete Mathematics 340, 7 (2017), 1705–1715.
  * [11] Colbourn, C. J., and Mathon, R. Steiner systems.  In Handbook of Combinatorial Designs. Chapman and Hall/CRC, 2006, pp. 128–135.
  * [12] Cornet, M. G., and Torres, P. $k$-tuple domination on Kneser graphs.  arXiv e-prints (2023), arXiv:2308.15603v1.
  * [13] Erdős, P., Ko, C., and Rado, R. Intersection theorem for system of finite sets.  Quart. J. Math. 12 (1961), 313–318.
  * [14] Fallat, S., Joshi, N., Maleki, R., Meagher, K., Mojallal, S. A., Nasserasr, S., Shirazi, M. N., Razafimahatratra, A. S., and Stevens, B. The $q$-analogue of zero forcing for certain families of graphs.  Discrete Applied Mathematics 348 (2024), 91–104.
  * [15] Gagarin, A., and Zverovich, V. E. A generalised upper bound for the $k$-tuple domination number.  Discrete Mathematics 308, 5-6 (2008), 880–885.
  * [16] Ghorbani, M., Klavžar, S., Maimani, H. R., Momeni, M., Mahid, F. R., and Rus, G. The general position problem on Kneser graphs and on some graph operations.  Discussiones Mathematicae Graph Theory 41 (2021), 1199–1213.
  * [17] Gorodezky, I. Dominating sets in Kneser graphs.  Master’s thesis, University of Waterloo, 2007.
  * [18] Grannell, M., and Griggs, T. An introduction to Steiner systems.  Mathematical Spectrum 26, 3 (1994), 74–80.
  * [19] Hammond, P., and Smith, D. Perfect codes in the graphs $O_{k}$.  Journal of Combinatorial Theory, Series B 19, 3 (1975), 239–255.
  * [20] Hartman, C., and West, D. B. Covering designs and domination in Kneser graphs.  unpublished manuscript (2003).
  * [21] Harvey, D. J., and Wood, D. R. Treewidth of the Kneser graph and the Erdös-Ko-Rado theorem.  The electronic Journal of Combinatorics 21:1 (2014), #P1.48.
  * [22] Haynes, T. W., Hedetniemi, S. T., and Henning, M. A. Topics in domination in graphs, vol. 64.  Springer, 2020.
  * [23] Haynes, T. W., Hedetniemi, S. T., and Slater, P. J., Eds.  Domination in graphs, vol. 209 of Monographs and Textbooks in Pure and Applied Mathematics.  Marcel Dekker, Inc., New York, 1998.  Advanced topics.
  * [24] Haynes, T. W., Hedetniemi, S. T., and Slater, P. J. Fundamentals of domination in graphs, vol. 208 of Monographs and Textbooks in Pure and Applied Mathematics.  Marcel Dekker, Inc., New York, 1998.
  * [25] IBM.  ILOG CPLEX Optimization Studio 22.1.0.  https://www.ibm.com/products/ilog-cplex-optimization-studio, 2022.  Accessed 2024-03-30.
  * [26] Ivančo, J., and Zelinka, B. Domination in Kneser graphs.  Mathematica Bohemica 118, 2 (1993), 147–152.
  * [27] Jalilolghadr, P., and Behtoei, A. Total dominator chromatic number of Kneser graphs.  AKCE International Journal of Graphs and Combinatorics 20, 1 (2023), 52–56.
  * [28] Junosza-Szaniawski, K., and Rzazewski, P. On the number of $2$-packings in a connected graph.  Discrete Mathematics 312, 23 (2012), 3444–3450.
  * [29] Kneser, M. Aufgabe 300.  Jahresbericht Deutschen Math. Verein 58, 2 (1955).
  * [30] Liao, C.-S., and Chang, G. J. $k$-tuple domination in graphs.  Information Processing Letters 87 (2003), 45–50.
  * [31] Lovász, L. Kneser’s conjecture, chromatic numbers and homotopy.  J. Combin. Theory (A) 25 (1978), 319–324.
  * [32] Matoušek, J. A combinatorial proof of Kneser’s conjecture.  Combinatorica 24 (2004), 163–170.
  * [33] Meir, A., and Moon, J. W. Relations between packing and covering numbers of a tree.  Pacific J. Math. 61, 1 (1975), 225–233.
  * [34] Östergård, P. R., Shao, Z., and Xu, X. Bounds on the domination number of Kneser graphs.  ARS MATHEMATICA CONTEMPORANEA 9, 2 (2014), 187–195.
  * [35] Przybyło, J. On upper bounds for multiple domination numbers of graphs.  Discrete Applied Mathematics 161, 16-17 (2013), 2758–2763.
  * [36] Ramanan, G. V. Proof of a conjecture of Frankl and Füredi.  journal of combinatorial theory, Series A 79, 1 (1997), 53–67.
  * [37] Rautenbach, D., and Volkmann, L. New bounds on the $k$-domination number and the $k$-tuple domination number.  Applied Mathematics Letters 20, 1 (2007), 98–102.
  * [38] Valencia-Pabon, M., and Vera, J.-C. On the diameter of Kneser graphs.  Discrete mathematics 305 (2005), 383–385.
  * [39] West, D. B., et al. Introduction to graph theory, vol. 2.  Prentice hall Upper Saddle River, 2001.
  * [40] Zec, T., and Grbić, M. Several Roman domination graph invariants on Kneser graphs.  Discrete Mathematics & Theoretical Computer Science 25:1, Graph Theory (2023).
  * [41] Zverovich, V. The $k$-tuple domination number revisited.  Applied Mathematics Letters 21, 10 (2008), 1005–1011.