ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2022) #P4.03 / 561–565
https://doi.org/10.26493/1855-3974.2600.dcc
(Also available at http://amc-journal.eu)
A note on the k-tuple domination number
of graphs*
Abel Cabrera Martı́nez
Universidad de Córdoba, Departamento de Matemáticas, Campus de Rabanales, 14071,
Córdoba, Spain
Received 9 April 2021, accepted 19 December 2021, published online 3 August 2022
Abstract
In a graph G, a vertex dominates itself and its neighbours. A set D ⊆ V (G) is said to
be a k-tuple dominating set of G if D dominates every vertex of G at least k times. The
minimum cardinality among all k-tuple dominating sets is the k-tuple domination number
of G. In this note, we provide new bounds on this parameter. Some of these bounds
generalize other ones that have been given for the case k = 2.
Keywords: k-domination, k-tuple domination.
Math. Subj. Class. (2020): 05C69
1 Introduction
Throughout this note we consider simple graphs G with vertex set V (G). Given a vertex
v ∈ V (G), N(v) denotes the open neighbourhood of v in G. In addition, for any set
D ⊆ V (G), the degree of v in D, denoted by degD(v), is the number of vertices in D
adjacent to v, i.e., degD(v) = |N(v) ∩D|. The minimum and maximum degrees of G will
be denoted by δ(G) and ∆(G), respectively. Other definitions not given here can be found
in standard graph theory books such as [12].
Domination theory in graphs have been extensively studied in the literature. For in-
stance, see the books [9, 10, 11]. A set D ⊆ V (G) is said to be a dominating set of G
if degD(v) ≥ 1 for every v ∈ V (G) \ D. The domination number of G is the minimum
cardinality among all dominating sets of G and it is denoted by γ(G). We define a γ(G)-set
as a dominating set of cardinality γ(G). The same agreement will be assumed for optimal
parameters associated to other characteristic sets defined in the paper.
*We are grateful to the anonymous reviewers for their useful comments on this note that improved its presen-
tation.
E-mail address: acmartinez@uco.es (Abel Cabrera Martı́nez)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
562 Ars Math. Contemp. 5 (2022) #P4.03 / 561–565
In 1985, Fink and Jacobson [4, 5] extended the idea of domination in graphs to the
more general notion of k-domination. A set D ⊆ V (G) is said to be a k-dominating set of
G if degD(v) ≥ k for every v ∈ V (G) \D. The k-domination number of G, denoted by
γk(G), is the minimum cardinality among all k-dominating sets of G. Subsequently, and
as expected, several variants for k-domination were introduced and studied by the scientific
community. In two different papers published in 1996 and 2000, Harary and Haynes [7, 8]
introduced the concept of double domination and, more generally, the concept of k-tuple
domination. Given a graph G and a positive integer k ≤ δ(G) + 1, a k-dominating set D
is said to be a k-tuple dominating set of G if degD(v) ≥ k − 1 for every v ∈ D. The
k-tuple domination number of G, denoted by γ×k(G), is the minimum cardinality among
all k-tuple dominating sets of G. The case k = 2 corresponds to double domination, in
such a case, γ×2(G) denotes the double domination number of graph G.
In this note, we provide new bounds on the k-tuple domination number. Some of these
bounds generalize other ones that have been given for the double domination number.
2 New bounds on the k-tuple domination number
Recently, Hansberg and Volkmann [6] put into context all relevant research results on mul-
tiple domination that have been found up to 2020. In that chapter, they posed the following
open problem.
Problem 2.1 ([6, Problem 5.8, p. 194]). Give an upper bound for γ×k(G) in terms of
γk(G) for any graph G of minimum degree δ(G) ≥ k − 1.
A fairly simple solution for the problem above is given by the straightforward rela-
tionship γ×k(G) ≤ kγk(G), which can be derived directly by constructing a set of ver-
tices D′ ⊆ V (G) of minimum cardinality from a γk(G)-set D such that D ⊆ D′ and
degD′(x) ≥ k − 1 for every vertex x ∈ D. From this construction above, it is easy to
check that D′ is a k-tuple dominating set of G and so,
γ×k(G) ≤ |D′| = |D|+ |D′ \D| ≤ |D|+ (k − 1)|D| = kγk(G).
This previous inequality was surely considered by Hansberg and Volkmann and, in that
sense, they have established the previous problem assuming that γ×k(G) < kγk(G) for
every graph G with δ(G) ≥ k − 1.
We next confirm their suspicions and provide a solution to Problem 2.1.
Theorem 2.2. Let k ≥ 2 be an integer. For any graph G with δ(G) ≥ k − 1,
γ×k(G) ≤ kγk(G)− (k − 1)2.
Proof. Let D be a γk(G)-set. As γ×k(G) ≤ |V (G)| we assume, without loss of generality,
that k|D| − (k− 1)2 ≤ |V (G)|. Now, let U = {u1, . . . , uk−1} ⊆ V (G) \D, D′ = D ∪U
and D0 = {v ∈ D : degD′(v) < k − 1}. The following inequalities arise from counting
arguments on the number of edges joining U with D0 and U with D \D0, respectively.
∑
v∈D0
degD′(v) ≥
k−1∑
i=1
degD0(ui) and |D \D0|(k − 1) ≥
k−1∑
i=1
degD\D0(ui).
A. Cabrera Martı́nez: A note on the k-tuple domination number of graphs 563
By the previous inequalities and the fact that D is a k-dominating set of G, we deduce that
∑
v∈D0
degD′(v) + |D \D0|(k − 1) ≥
k−1∑
i=1
degD0(ui) +
k−1∑
i=1
degD\D0(ui)
=
k−1∑
i=1
degD(ui)
≥ k(k − 1).
Now, we define D′′ ⊆ V (G) as a set of minimum cardinality among all supersets W of D′
such that degW (x) ≥ k − 1 for every vertex x ∈ D. Since degD′(x) ≥ k − 1 for every
x ∈ D \ D0, the condition on W is equivalent to that every vertex v ∈ D0 has at least
k−1−degD′(v) neighbours in W \D. Hence, by the minimality of D′′ and the inequality
chain above, we deduce that
|D′′ \D′| ≤ |D0|(k − 1)−
∑
v∈D0
degD′(v)
= |D|(k − 1)−
(∑
v∈D0
degD′(v) + |D \D0|(k − 1)
)
≤ |D|(k − 1)− k(k − 1).
Moreover, it is easy to check that D′′ is a k-tuple dominating set of G because each vertex
in V (G) \D is dominated k times by vertices of D ⊆ D′′ (recall that D is a k-dominating
set of G) and the construction of D′′ ensures that each vertex in D is dominated k times by
vertices of D′′. Hence,
γ×k(G) ≤ |D′′| = |D′|+ |D′′ \D′|
≤ |D|+ k − 1 + |D|(k − 1)− k(k − 1)
= kγk(G)− (k − 1)2,
which completes the proof.
The bound above is tight. For instance, it is achieved by any complete bipartite graph
Kk,k′ with k′ ≥ k, as γ×k(Kk,k′) = 2k−1 and γk(Kk,k′) = k. When k = 2, Theorem 2.2
leads to the relationship γ×2(G) ≤ 2γ2(G)− 1 given in 2018 by Bonomo et al. [1].
A set D ⊆ V (G) is a 2-packing of a graph G if N [u] ∩ N [v] = ∅ for every pair of
different vertices u, v ∈ D. The 2-packing number of G, denoted by ρ(G), is the maximum
cardinality among all 2-packings of G.
The next theorem relates the k-tuple domination number with the 2-packing number
of a graph. Note that the bounds given in this result are generalizations of the bounds
γ×2(G) ≥ 2ρ(G) due to Chellali et al. [3], and γ×2(G) ≤ |V (G)| − ρ(G) due to Chellali
and Haynes [2].
Theorem 2.3. Let k ≥ 2 be an integer. For any graph G of order n and δ(G) ≥ k,
kρ(G) ≤ γ×k(G) ≤ n− ρ(G).
564 Ars Math. Contemp. 5 (2022) #P4.03 / 561–565
Proof. Let D be a ρ(G)-set and S a γ×k(G)-set. Since degS(v) ≥ k for every v ∈ D \ S,
and degS(v) ≥ k − 1 for every v ∈ D ∩ S, we deduce that
γ×k(G) = |S| ≥
∑
v∈D\S
degS(v) +
∑
v∈D∩S
(degS(v) + 1) ≥ k|D| = kρ(G),
and the lower bound follows.
Next, let us proceed to prove that V (G) \ D is a k-tuple dominating set of G. Since
δ(G) ≥ k, N(D) ∩ D = ∅ and degD(x) ≤ 1 for every x ∈ V (G) \ D, we deduce that
degV (G)\D(v) ≥ k for every v ∈ D and degV (G)\D(v) ≥ k − 1 for every v ∈ V (G) \D.
Hence, V (G) \D is a k-tuple dominating set of G, as desired.
Therefore, γ×k(G) ≤ |V (G) \D| = n− ρ(G), which completes the proof.
Let H be the family of graphs Hk,r defined as follows. For any pair of integers k, r ∈ Z,
with k ≥ 2 and r ≥ 1, the graph Hk,r is obtained from a complete graph Kkr and an
empty graph rK1 such that V (Hk,r) = V (Kkr) ∪ V (rK1), V (Kkr) = {v1, . . . , vkr} and
V (rK1) = {u1, . . . , ur} and E(Hk,r) = E(Kkr) ∪ (
⋃r−1
i=0 {ui+1vki+1, . . . , ui+1vki+k}).
Figure 1 shows a graph of this family. Observe that |V (Hk,r)| = r(k+1), γ×k(Hk,r) = kr
and ρ(Hk,r) = r for every Hk,r ∈ H. Therefore, for these graphs the bounds given in
Theorem 2.3 are tight, i.e., γ×k(Hk,r) = kρ(Hk,r) = |V (Hk,r)| − ρ(Hk,r).
Figure 1: The graph H4,2 ∈ H.
In [8], Harary and Haynes showed that γ×k(G) ≥ 2kn−2mk+1 for any graph G of order n
and size m with δ(G) ≥ k − 1. The next result is a partial refinement of the bound above
because it only considers graphs with minimum degree at least k.
Proposition 2.4. Let k ≥ 2 be an integer. For any graph G of order n and size m with
δ(G) ≥ k,
γ×k(G) ≥
(δ(G) + k)n− 2m
δ(G) + 1
.
Proof. Let S be a γ×k(G)-set and S = V (G) \ S. Hence,
2m =
∑
v∈S
degS(v) + 2
∑
v∈S
degS(v) +
∑
v∈S
degS(v)
=
∑
v∈S
degS(v) +
∑
v∈S
degS(v) +
∑
v∈S
degV (G)(v)
≥ (k − 1)|S|+ k(n− |S|) + δ(G)(n− |S|)
= (k − 1)|S|+ (δ(G) + k)(n− |S|)
= (δ(G) + k)n− (δ(G) + 1)|S|,
A. Cabrera Martı́nez: A note on the k-tuple domination number of graphs 565
which implies that |S| ≥ (δ(G)+k)n−2mδ(G)+1 . Therefore, the proof is complete.
The bound above is tight. For instance, it is achieved for the join graph G = Kk + Ck
obtained from the complete graph Kk and the cycle graph Ck, with k ≥ 3. For this case,
we have that γ×k(G) = k, |V (G)| = 2k, δ(G) = k + 2 and 2|E(G)| = 3k2 + k. Also, it
is achieved for the complete graph Kn (n ≥ 3) and any k ∈ {2, . . . , n− 1}.
ORCID iDs
Abel Cabrera Martı́nez https://orcid.org/0000-0003-2806-4842
References
[1] F. Bonomo, B. Brešar, L. N. Grippo, M. Milanič and M. D. Safe, Domination parameters with
number 2: interrelations and algorithmic consequences, Discrete Appl. Math. 235 (2018), 23–
50, doi:10.1016/j.dam.2017.08.017.
[2] M. Chellali and T. W. Haynes, On paired and double domination in graphs, Util. Math. 67
(2005), 161–171.
[3] M. Chellali, A. Khelladi and F. Maffray, Exact double domination in graphs, Discuss. Math.
Graph Theory 25 (2005), 291–302, doi:10.7151/dmgt.1282.
[4] J. F. Fink and M. S. Jacobson, n-domination in graphs, in: Graph Theory with Applications
to Algorithms and Computer Science (Kalamazoo, Mich., 1984), Wiley, New York, Wiley-
Intersci. Publ., pp. 283–300, 1985.
[5] J. F. Fink and M. S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, in:
Graph Theory with Applications to Algorithms and Computer Science (Kalamazoo, Mich.,
1984), Wiley, New York, Wiley-Intersci. Publ., pp. 301–311, 1985.
[6] A. Hansberg and L. Volkmann, Multiple domination, in: Topics in Domination in
Graphs, Springer, Cham, volume 64 of Dev. Math., pp. 151–203, 2020, doi:10.1007/
978-3-030-51117-3\ 6.
[7] F. Harary and T. W. Haynes, Nordhaus-Gaddum inequalities for domination in graphs, volume
155, pp. 99–105, 1996, doi:10.1016/0012-365x(94)00373-q.
[8] F. Harary and T. W. Haynes, Double domination in graphs, Ars Comb. 55 (2000), 201–213.
[9] T. W. Haynes, S. T. Hedetniemi and M. A. Henning (eds.), Topics in domination in
graphs, volume 64 of Developments in Mathematics, Springer, Cham, 2020, doi:10.1007/
978-3-030-51117-3.
[10] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs, Advanced Topics,
Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc., New York,
1998, doi:10.1201/9781315141428.
[11] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, vol-
ume 208 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc.,
New York, 1998, doi:10.1201/9781482246582.
[12] D. B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996,
https://faculty.math.illinois.edu/˜west/igt/index.html.