ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P1.04 / 57–81
https://doi.org/10.26493/1855-3974.2318.fb9
(Also available at http://amc-journal.eu)
From Italian domination in lexicographic
product graphs to w-domination in graphs*
Abel Cabrera Martı́nez , Alejandro Estrada-Moreno ,
Juan Alberto Rodrı́guez-Velázquez
Universitat Rovira i Virgili, Departament d’Enginyeria Informàtica i Matemàtiques,
Av. Paı̈sos Catalans 26, 43007 Tarragona, Spain
Received 23 April 2020, accepted 9 May 2021, published online 18 February 2022
Abstract
In this paper, we show that the Italian domination number of every lexicographic prod-
uct graph G ◦ H can be expressed in terms of five different domination parameters of G.
These parameters can be defined under the following unified approach, which encompasses
the definition of several well-known domination parameters and introduces new ones.
Let N(v) denote the open neighbourhood of v ∈ V (G), and let w = (w0, w1, . . . , wl)
be a vector of nonnegative integers such that w0 ≥ 1. We say that a function f : V (G) →
{0, 1, . . . , l} is a w-dominating function if f(N(v)) =
∑
u∈N(v) f(u) ≥ wi for every
vertex v with f(v) = i. The weight of f is defined to be ω(f) =
∑
v∈V (G) f(v). The
w-domination number of G, denoted by γw(G), is the minimum weight among all w-
dominating functions on G.
Specifically, we show that γI(G ◦ H) = γw(G), where w ∈ {2} × {0, 1, 2}l and
l ∈ {2, 3}. The decision on whether the equality holds for specific values of w0, . . . , wl will
depend on the value of the domination number of H . This paper also provides preliminary
results on γw(G) and raises the challenge of conducting a detailed study of the topic.
Keywords: Italian domination, w-domination, k-domination, k-tuple domination, lexicographic prod-
uct graph.
Math. Subj. Class. (2020): 05C69, 05C76
*The authors would thank the anonymous reviewers for their generous time in providing detailed comments
and suggestions that helped us to improve the paper.
E-mail addresses: abel.cabrera@urv.cat (Abel Cabrera Martı́nez), alejandro.estrada@urv.cat (Alejandro
Estrada-Moreno), juanalberto.rodriguez@urv.cat (Juan Alberto Rodrı́guez-Velázquez)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
58 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
1 Introduction
Let G be a graph, l a positive integer, and f : V (G) → {0, . . . , l} a function. For every
i ∈ {0, . . . , l}, we define Vi = {v ∈ V (G) : f(v) = i}. We will identify f with the
subsets V0, . . . , Vl associated with it, and so we will use the unified notation f(V0, . . . , Vl)
for the function and these associated subsets. The weight of f is defined to be
ω(f) = f(V (G)) =
l∑
i=1
i|Vi|.
An Italian dominating function (IDF) on a graph G is a function f(V0, V1, V2) satisfy-
ing that f(N(v)) =
∑
u∈N(v) f(u) ≥ 2 for every v ∈ V0, where N(v) denotes the open
neighbourhood of v. Hence, f(V0, V1, V2) is an IDF if N(v)∩V2 ̸= ∅ or |N(v)∩V1| ≥ 2
for every v ∈ V0. The Italian domination number, denoted by γI(G), is the minimum
weight among all IDFs on G. This concept was introduced by Chellali et al. in [6] under
the name of Roman {2}-domination. The term “Italian domination” comes from a subse-
quent paper by Henning and Klostermeyer [13].
In this paper we show that the Italian domination number of every lexicographic product
graph G◦H can be expressed in terms of five different domination parameters of G. These
parameters can be defined under the following unified approach.
Let w = (w0, . . . , wl) be a vector of nonnegative integers such that w0 ≥ 1. We say
that f(V0, . . . , Vl) is a w-dominating function if f(N(v)) ≥ wi for every v ∈ Vi. The
w-domination number of G, denoted by γw(G), is the minimum weight among all w-
dominating functions on G. For simplicity, a w-dominating function f of weight ω(f) =
γw(G) will be called a γw(G)-function.
This unified approach allows us to encompass the definition of several well-known
domination parameters and introduce new ones. For instance, we would highlight the fol-
lowing particular cases of known domination parameters that we define here in terms of
w-domination.
• The domination number of G is defined to be γ(G) = γ(1,0)(G) = γ(1,0,0)(G).
Obviously, every γ(1,0,0)(G)-function f(V0, V1, V2) satisfies that V2 = ∅ and V1 is
a dominating set of cardinality |V1| = γ(G), i.e., V1 is a γ(G)-set.
• The total domination number of a graph G with no isolated vertex is defined to be
γt(G) = γ(1,1)(G) = γ(1,1,w2,...,wl)(G), for every w2, . . . , wl ∈ {0, 1}. Notice
that there exists a γ(1,1,w2,...,wl)(G)-function f(V0, V1, . . . , Vl) such that Vi = ∅ for
every i ∈ {2, . . . , l} and V1 is a total dominating set of cardinality |V1| = γt(G),
i.e., V1 is a γt(G)-set.
• Given a positive integer k, the k-domination number of a graph G is defined to be
γk(G) = γ(k,0)(G). In this case, V1 is a k-dominating set of cardinality |V1| =
γk(G), i.e., V1 is a γk(G)-set. The study of k-domination in graphs was initiated by
Fink and Jacobson [8] in 1984.
• Given a positive integer k, the k-tuple domination number of a graph G of minimum
degree δ ≥ k−1 is defined to be γ×k(G) = γ(k,k−1)(G). In this case, V1 is a k-tuple
dominating set of cardinality |V1| = γ×k(G), i.e., V1 is a γ×k(G)-set. In particular,
γ×1(G) = γ(G) and γ×2(G) is known as the double domination number of G. This
parameter was introduced by Harary and Haynes in [9].
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 59
• Given a positive integer k, the k-tuple total domination number of a graph G of
minimum degree δ ≥ k is defined to be γ×k,t(G) = γ(k,k)(G). In particular,
γ×1,t(G) = γt(G) and γ×2,t(G) is known as the double total domination number,
and V1 is a double total dominating set of cardinality |V1| = γ×2,t(G), i.e., V1 is a
γ×2,t(G)-set. The k-tuple total domination number was introduced by Henning and
Kazemi in [12].
• The Italian domination number of G is defined to be γ
I
(G) = γ(2,0,0)(G). As
mentioned earlier, this parameter was introduced by Chellali et al. in [6] under
the name of Roman {2}-domination number. The concept was studied further
in [13, 16].
• The total Italian domination number of a graph G with no isolated vertex is defined
to be γtI(G) = γ(2,1,1)(G). This parameter was introduced by Cabrera et al. in
[4], and independently by Abdollahzadeh Ahangar et al. in [1], under the name of
total Roman {2}-domination number. The total Italian domination number of lexi-
cographic product graphs was studied in [5].
• The {k}-domination number of G is defined to be γ{k}(G) = γ(k,k−1,...,1,0)(G).
This parameter was introduced by Domke et al. in [7] and studied further
in [3, 15, 17].
Notice that the concept of Y -dominating function introduced by Bange et al. [2] is quite
different from the concept of w-dominating function introduced in this paper. Given a set
Y of real numbers, a function f : V (G) → Y is a Y -dominating function if f(N [v]) =
f(v) +
∑
u∈N(v) f(u) ≥ 1 for every v ∈ V (G). The Y -domination number, denoted
by γ
Y
(G), is the minimum weight among all Y -dominating functions on G. Hence, if
Y = {0, 1, . . . , l}, then γ
Y
(G) = γ(1,0,...,0)(G) = γ(G).
For the graphs shown in Figure 1 we have the following values.
• γI(G1) = γ(2,1,0)(G1) = γ(2,2,0)(G1) = 4 < 6 = γ(2,2,1)(G1) = γ(2,2,2)(G1).
• γI(G2) = γ(2,1,0)(G2) = γ(2,2,0)(G2) = γ(2,2,1)(G2) = γ(2,2,2)(G2) = 3.
• γI(G3) = γ(2,1,0)(G3) = 6 < 8 = γ(2,2,0)(G3) = γ(2,2,1)(G3) = γ(2,2,2)(G3).
11
1 1
G1
1
1
1
G2
22
2 2
G3
Figure 1: The labels of black-coloured vertices describe a γ(2,1,0)(G1)-function, a
γ(2,2,0)(G2)-function and a γ(2,2,2)(G3)-function, respectively.
60 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
The remainder of the paper is organized as follows. In Section 2 we show that for any
graph G with no isolated vertex and any nontrivial graph H with γ(H) ̸= 3 or γ
I
(H) ̸= 3,
the Italian domination number of G◦H equals one of the following parameters: γ(2,1,0)(G),
γ(2,2,0)(G), γ(2,2,1)(G) or γ(2,2,2)(G). The specific value γI (G ◦H) takes depends on the
value of γ(H). For the cases where γ
I
(H) = γ(H) = 3, we show that γ
I
(G ◦ H) =
γ(2,2,2,0)(G). Section 3 is devoted to providing some preliminary results on w-domination.
We first describe some general properties of γw(G) and then dedicate a subsection to each
of the specific cases declared of interest in Section 2.
We assume that the reader is familiar with the basic concepts, notation and terminology
of domination in graph. If this is not the case, we suggest the textbooks [10, 11, 14]. For
the remainder of the paper, definitions will be introduced whenever a concept is needed.
2 Italian domination in lexicographic product graphs
The lexicographic product of two graphs G and H is the graph G ◦H whose vertex set is
V (G ◦ H) = V (G) × V (H) and (u, v)(x, y) ∈ E(G ◦ H) if and only if ux ∈ E(G) or
u = x and vy ∈ E(H).
Notice that for any u ∈ V (G) the subgraph of G ◦ H induced by {u} × V (H) is
isomorphic to H . For simplicity, we will denote this subgraph by Hu. Moreover, the
neighbourhood of (x, y) ∈ V (G)×V (H) will be denoted by N(x, y) instead of N((x, y)).
Analogously, for any function f on G ◦H , the image of (x, y) will be denoted by f(x, y)
instead of f((x, y)).
Lemma 2.1. For any graph G with no isolated vertex and any nontrivial graph H with
γ
I
(H) ̸= 3 or γ(H) ̸= 3, there exists a γ
I
(G◦H)-function f satisfying that f(V (Hu)) ≤ 2
for every u ∈ V (G).
Proof. Given an IDF f on G ◦H , we define the set Rf = {x ∈ V (G) : f(V (Hx)) ≥ 3}.
Let f be a γ
I
(G ◦H)-function such that |Rf | is minimum among all γI (G ◦H)-functions.
Suppose that |Rf | ≥ 1. Let u ∈ Rf such that f(V (Hu)) is maximum among all vertices
belonging to Rf . Suppose that f(V (Hu)) > γI (H). In this case we take a γI (H)-function
h and construct an IDF g defined on G ◦ H as g(u, y) = h(y) for every y ∈ V (H) and
g(x, y) = f(x, y) for every x ∈ V (G) \ {u} and y ∈ V (H). Obviously, ω(g) < ω(f),
which is a contradiction. Thus, 3 ≤ f(V (Hu)) ≤ γI (Hu) = γI (H). Now, we analyse the
following two cases.
Case 1. f(V (Hu)) ≥ 4. Let u′ ∈ N(u) and v ∈ V (H). We define a function f ′ on G ◦H
as f ′(u, v) = f ′(u′, v) = 2, f ′(u, y) = f(u′, y) = 0 for every y ∈ V (H) \ {v}, and
f ′(x, y) = f(x, y) for every x ∈ V (G) \ {u, u′} and y ∈ V (H). Notice that f ′ is an IDF
on G ◦H with ω(f ′) ≤ ω(f) and |Rf ′ | < |Rf |, which is a contradiction.
Case 2. f(V (Hu)) = 3. Suppose that γI (H) ̸= 3. Since γI (H) ≥ 4, there exist u′ ∈
N(u) and v ∈ V (H) such that f(u′, v) ≥ 1. Hence, the function f ′ defined in Case 1 is an
IDF on G ◦H with ω(f ′) ≤ ω(f) and |Rf ′ | < |Rf |, which is again a contradiction.
Thus, γ
I
(H) = 3, and so γ(H) ̸= 3, which implies that γ(H) = 2. Let {v1, v2} be
a γ(H)-set. Let u′ ∈ N(u) and v′ ∈ V (H) such that f(u′, v′) = max{f(u′, y) : y ∈
V (H)}. Consider the function f ′ defined as f ′(u, v1) = f ′(u, v2) = 1, f ′(u, y) = 0 for
every y ∈ V (H) \ {v1, v2}, f ′(u′, v′) = min{2, f(u′, v′) + 1}, f ′(u′, y) = 0 for every
y ∈ V (H) \ {v′}, and f ′(x, y) = f(x, y) for every x ∈ V (G) \ {u, u′} and y ∈ V (H).
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 61
Notice that f ′ is an IDF on G ◦ H with ω(f ′) ≤ ω(f) and |Rf ′ | < |Rf |, which is a
contradiction.
Therefore, Rf = ∅, and the result follows.
Theorem 2.2. The following statements hold for any graph G with no isolated vertex and
any nontrivial graph H with γ
I
(H) ̸= 3 or γ(H) ̸= 3.
(i) If γ(H) = 1, then γ
I
(G ◦H) = γ(2,1,0)(G).
(ii) If γ2(H) = γ(H) = 2, then γI (G ◦H) = γ(2,2,0)(G).
(iii) If γ2(H) > γ(H) = 2, then γI (G ◦H) = γ(2,2,1)(G).
(iv) If γ(H) ≥ 3, then γ
I
(G ◦H) = γ(2,2,2)(G).
Proof. Let f(V0, V1, V2) be a γI(G ◦H)-function which satisfies Lemma 2.1. Let f ′(X0,
X1, X2) be the function defined on G by X1 = {x ∈ V (G) : f(V (Hx)) = 1} and
X2 = {x ∈ V (G) : f(V (Hx)) = 2}. Notice that γI (G ◦H) = ω(f) = ω(f ′). We claim
that f ′ is a γ(w0,w1,w2)(G)-function. In order to prove this and find the values of w0, w1
and w2, we differentiate the following three cases.
Case 1. γ(H) = 1. Assume that x ∈ X0. Since f(V (Hx)) = 0, for any y ∈ V (H) we
have that f(N(x, y) \ V (Hx)) ≥ 2. Thus, f ′(N(x)) ≥ 2. Now, assume that x ∈ X1,
and let (x, y) ∈ V1 be the only vertex in V (Hx) such that f(x, y) > 0. Since γ(H) = 1,
for any z ∈ V (H) \ {y}, we have that f(N(x, z) \ V (Hx)) ≥ 1, which implies that
f ′(N(x)) ≥ 1. Therefore, f ′ is a (2, 1, 0)-dominating function on G and, as a consequence,
γ
I
(G ◦H) = ω(f) = ω(f ′) ≥ γ(2,1,0)(G).
Now, for any γ(2,1,0)(G)-function g(W0,W1,W2) and any universal vertex v of H , the
function g′(W ′0,W
′
1,W
′
2), defined by W
′
2 = W2 × {v} and W ′1 = W1 × {v}, is an IDF on
G ◦H . Therefore, γ
I
(G ◦H) ≤ ω(g′) = ω(g) = γ(2,1,0)(G).
Case 2. γ(H) = 2. As in Case 1 we conclude that f ′(N(x)) ≥ 2 for every x ∈ X0. Now,
assume that x ∈ X1, and let (x, y) ∈ V1 be the only vertex in V (Hx) such that f(x, y) >
0. Since γ(H) = 2, there exists a vertex z ∈ V (H) such that (x, z) ∈ V0 \ N(x, y).
Hence, f(N(x, z) \ V (Hx)) ≥ 2, which implies that f ′(N(x)) ≥ 2. Therefore, f ′ is a
(2, 2, 0)-dominating function on G and, as a consequence, γ
I
(G ◦H) = ω(f) = ω(f ′) ≥
γ(2,2,0)(G).
Now, if γ2(H) > γ(H) = 2, then for every x ∈ X2, there exists y ∈ V (H) such that
(x, y) ∈ V0 and f(N(x, y)∩V (Hx)) ≤ 1, which implies that f(N(x, y)\V (Hx)) ≥ 1, and
so f ′(N(x)) ≥ 1. Hence, f ′ is a (2, 2, 1)-dominating function on G and, as a consequence,
γ
I
(G ◦H) = ω(f) = ω(f ′) ≥ γ(2,2,1)(G).
On the other side, if γ2(H) = 2, then for any γ(2,2,0)(G)-function g(W0,W1,W2)
and any γ2(H)-set S = {v1, v2}, the function g′(W ′0,W ′1,W ′2), defined by W ′1 = (W1 ×
{v1}) ∪ (W2 × S) and W ′2 = ∅, is an IDF on G ◦H . Therefore, γI (G ◦H) ≤ ω(g′) =
ω(g) = γ(2,2,0)(G).
Finally, if γ2(H) > γ(H) = 2 then we take a γ(2,2,1)(G)-function h(Y0, Y1, Y2) and
a γ(H)-set S′ = {v′1, v′2}, and construct a function h′(Y ′0 , Y ′1 , Y ′2) on G ◦ H by making
Y ′1 = (Y1 × {v′1}) ∪ (Y2 × S′) and Y ′2 = ∅. Obviously, h′ is an IDF on G ◦H , and so we
can conclude that γ
I
(G ◦H) ≤ ω(h′) = ω(h) = γ(2,2,1)(G).
62 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
Case 3. γ(H) ≥ 3. In this case, for every x ∈ V (G), there exists y ∈ V (H) such
that f(N [(x, y)] ∩ V (Hx)) = 0. Hence, f(N(x, y) \ V (Hx)) ≥ 2, which implies that
f ′(N(x)) ≥ 2 for every x ∈ V (G). Therefore, f ′ is a (2, 2, 2)-dominating function on G
and, as a consequence, γ
I
(G ◦H) = ω(f) = ω(f ′) ≥ γ(2,2,2)(G).
On the other side, for any γ(2,2,2)(G)-function g(W0,W1,W2) and any v ∈ V (H), the
function g′(W ′0,W
′
1,W
′
2), defined by W
′
2 = W2 × {v} and W ′1 = W1 × {v}, is an IDF on
G ◦H . Hence, γ
I
(G ◦H) ≤ ω(g′) = ω(g) = γ(2,2,2)(G).
According to the three cases above, the result follows.
The following result considers the case γ
I
(H) = γ(H) = 3.
Theorem 2.3. If H is a graph with γ
I
(H) = γ(H) = 3, then for any graph G,
γ
I
(G ◦H) = γ(2,2,2,0)(G).
Proof. Let f(V0, V1, V2) be a γI(G ◦ H)-function, and f ′(X0, X1, X2, X3) the function
defined on G by X1 = {x ∈ V (G) : f(V (Hx)) = 1}, X2 = {x ∈ V (G) : f(V (Hx)) =
2} and X3 = {x ∈ V (G) : f(V (Hx)) ≥ 3}. We claim that f ′ is a (2, 2, 2, 0)-dominating
function on G.
Let x ∈ X0 ∪X1 ∪X2. Since f(V (Hx)) ≤ 2 and γ(H) = 3, there exists y ∈ V (H)
such that f(N [(x, y)] ∩ V (Hx)) = 0. Thus, f ′(N(x)) ≥ 2 for every x ∈ X0 ∪X1 ∪X2,
which implies that f ′ is a (2, 2, 2, 0)-dominating function on G. Therefore, γ
I
(G ◦H) =
ω(f) ≥ ω(f ′) ≥ γ(2,2,2,0)(G).
On the other side, let h(Y0, Y1, Y2, Y3) be a γ(2,2,2,0)(G)-function, h1 a γI (H)-function
and v ∈ V (H). We define a function g on G◦H by g(x, v) = h(x) for every x ∈ V (G)\Y3,
g(x, y) = 0 for every x ∈ V (G) \ Y3 and y ∈ V (H) \ {v}, and g(x, y) = h1(y) for every
(x, y) ∈ Y3 × V (H). A simple case analysis shows that g is an IDF on G ◦H . Therefore,
γ
I
(G ◦H) ≤ ω(g) = ω(h) = γ(2,2,2,0)(G).
The graph shown in Figure 2 satisfies 6 = γ(2,2,0)(G) = γ(2,2,1)(G) < 7 =
γ(2,2,2,0)(G) < γ(2,2,2)(G) = 8.
2 1 1 2 2 2 2
Figure 2: This figure shows two γ(2,2,0)(G)-functions on the same graph. The function on
the left is also a γ(2,2,1)(G)-function.
3 Preliminary results on w-domination
In this section, we fix the notation Z+ = {1, 2, 3, . . .} and N = Z+ ∪ {0} for the sets of
positive and nonnegative integers, respectively.
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 63
Throughout this section, we will repeatedly apply, without explicit mention, the follo-
wing necessary and sufficient condition for the existence of a w-dominating function.
Remark 3.1. Let G be a graph of minimum degree δ and let w = (w0, . . . , wl) ∈ Z+×Nl.
If w0 ≥ · · · ≥ wl, then there exists a w-dominating function on G if and only if wl ≤ lδ.
Proof. Let w = (w0, . . . , wl) ∈ Z+ × Nl such that w0 ≥ · · · ≥ wl. If wl ≤ lδ, then the
function f , defined by f(v) = l for every v ∈ V (G), is a w-dominating function on G, as
Vl = V (G) and for any x ∈ Vl, f(N(x)) ≥ lδ ≥ wl.
Now, suppose that wl > lδ. If g is a w-dominating function on G, then for any vertex
v of degree δ we have g(N(v)) ≤ δl < wl ≤ wl−1 ≤ · · · ≤ w0, which is a contradiction.
Therefore, the result follows.
We will show that in general the w-domination numbers satisfy a certain monotonicity.
Given two integer vectors w = (w0, . . . , wl) and w′ = (w′0, . . . , w
′
l), we say that w ≺ w′ if
wi ≤ w′i for every i ∈ {0, . . . , l}. With this notation in mind, we can state the next remark
which is direct consequence of the definition of w-domination number.
Remark 3.2. Let G be a graph of minimum degree δ and let w = (w0, . . . , wl), w′ =
(w′0, . . . , w
′
l) ∈ Z+×Nl such that wi ≥ wi+1 and w′i ≥ w′i+1 for every i ∈ {0, . . . , l−1}.
If w ≺ w′ and w′l ≤ lδ, then every w′-dominating function is a w-dominating function
and, as a consequence,
γw(G) ≤ γw′(G).
We would emphasize the following remark on the specific cases of domination param-
eters considered in Section 2. Obviously, when we write γ(2,2,2)(G) or γ(2,2,1)(G), we are
assuming that G has minimum degree δ ≥ 1.
Remark 3.3. The following statements hold.
(i) γ
I
(G) = γ(2,0,0)(G) ≤ γ(2,1,0)(G) ≤ γ(2,2,0)(G) ≤ γ(2,2,1)(G) ≤ γ(2,2,2)(G).
(ii) If w2 ∈ {1, 2}, then γ(1,0,w2)(G) = γ(1,0,0)(G) = γ(G) and γ(1,1,w2)(G) =
γ(1,1,0)(G) = γt(G).
(iii) For any integer k ≥ 3, there exists an infinite family Hk of graphs such that for every
graph G ∈ Hk, γI (G) = γ(2,0,0)(G) = γ(2,1,0)(G) = γ(2,2,0)(G) = γ(2,2,1)(G) =
γ(2,2,2)(G) = k.
(iv) There exists an infinite family of graphs such that γ
I
(G) < γ(2,1,0)(G) <
γ(2,2,0)(G) < γ(2,2,1)(G) < γ(2,2,2)(G).
In order to see that the remark above holds, we just have to construct families of graphs
satisfying (iii) and (iv), as (i) is a particular case of Remark 3.2 and (ii) is derived from
the definition of (w0, w1, w2)-domination number. In the case of (iii), we construct a fam-
ily Hk = {Gk,r : r ∈ Z+} as follows. Let k ≥ 3 be an integer, and let Nr be the
empty graph of order r. For any positive integer r we construct a graph Gk,r ∈ Hk
from a complete graph Kk and
(
k
2
)
copies of Nr, in such way that for each pair of dif-
ferent vertices {x, y} of Kk we choose one copy of Nr and connect every vertex of Nr
with x and y, making x and y vertices of degree (k − 1)(r + 1) in Gk,r. For instance,
the graph G3,1 is isomorphic to the graph G2 shown in Figure 1. It is readily seen that
64 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
γ
I
(Gk,r) = γ(2,2,2)(Gk,r) = k. On the other hand, in the case of (iv), we consider the
family of cycles of order n ≥ 10 with n ≡ 1 (mod 3). For these graphs we have that
γI(Cn) < γ(2,1,0)(Cn) < γ(2,2,0)(Cn) < γ(2,2,1)(Cn) < γ(2,2,2)(Cn). The specific values
of γ(w0,w1,w2)(Cn) will be given in Subsections 3.1 – 3.4.
Next we show a class of graphs where γ(w0,...,wl)(G) = w0γ(G) whenever l ≥ w0 ≥
· · · ≥ wl. To this end, we need to introduce some additional notation and terminology.
Given two graphs G1 and G2, the corona product graph G1 ⊙ G2 is the graph obtained
from G1 and G2, by taking one copy of G1 and |V (G1)| copies of G2 and joining by an
edge every vertex from the ith-copy of G2 with the ith-vertex of G1. For every x ∈ V (G1),
the copy of G2 in G1 ⊙G2 associated to x will be denoted by G2,x. It is well known that
γ(G1 ⊙ G2) = |V (G1)| and, if G1 does not have isolated vertices, then γt(G1 ⊙ G2) =
γ(G1 ⊙G2) = |V (G1)|.
Theorem 3.4. Let G ∼= G1 ⊙ G2 be a corona graph where G1 does not have isolated
vertices, and let w = (w0, . . . , wl) ∈ Z+ × Nl. If l ≥ w0 ≥ · · · ≥ wl and |V (G2)| ≥ w0,
then
γw(G) = w0γ(G).
Proof. Since G1 does not have isolated vertices, the upper bound γw(G) ≤ w0|V (G1)| =
w0γ(G) is straightforward, as the function f , defined by f(x) = w0 for every vertex
x ∈ V (G1) and f(x) = 0 for every x ∈ V (G) \ V (G1), is a w-dominating function on G.
On the other hand, let f be a γw(G)-function and suppose that there exists x ∈ V (G1)
such that f(V (G2,x)) + f(x) ≤ w0 − 1. In such a case, f(N [y]) ≤ w0 − 1 for every
y ∈ V (G2,x), which is a contradiction, as |V (G2)| ≥ w0. Therefore, γw(G) = ω(f) ≥
w0|V (G1)| = w0γ(G).
Proposition 3.5. Let G be a graph of order n. Let w = (w0, . . . , wl) ∈ Z+ ×Nl such that
w0 ≥ · · · ≥ wl. If G′ is a spanning subgraph of G with minimum degree δ′ ≥ wll , then
γw(G) ≤ γw(G′).
Proof. Let E− = {e1, . . . , ek} be the set of all edges of G not belonging to the edge set of
G′. Let G′0 = G and, for every i ∈ {1, . . . , k}, let Xi = {e1, . . . , ei} and G′i = G −Xi,
the edge-deletion subgraph of G induced by E(G) \Xi. Since any w-dominating function
on G′i is a w-dominating function on G
′
i−1, we can conclude that γw(G
′
i−1) ≤ γw(G′i).
Hence, γw(G) = γw(G′0) ≤ γw(G′1) ≤ · · · ≤ γw(G′k) = γw(G′).
From Proposition 3.5 we obtain the following result.
Corollary 3.6. Let G be a graph of order n and w = (w0, . . . , wl) ∈ Z+ × Nl such that
w0 ≥ · · · ≥ wl.
• If G is a Hamiltonian graph and wl ≤ 2l, then γw(G) ≤ γw(Cn).
• If G has a Hamiltonian path and wl ≤ l, then γw(G) ≤ γw(Pn).
In order to derive lower bounds on the w-domination number, we need to state the
following useful lemma.
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 65
Lemma 3.7. Let G be a graph with no isolated vertex, maximum degree ∆ and order n.
For any w-dominating function f(V0, . . . , Vl) on G such that w0 ≥ · · · ≥ wl,
∆ω(f) ≥ w0n+
l∑
i=1
(wi − w0)|Vi|.
Proof. The result follows from the simple fact that the contribution of any vertex x ∈ V (G)
to the sum
∑
x∈V (G) f(N(x)) equals deg(x)f(x), where deg(x) denotes the degree of x.
Hence,
∆ω(f) = ∆
∑
x∈V (G)
f(x)
≥
∑
x∈V (G)
deg(x)f(x)
=
∑
x∈V (G)
f(N(x))
≥ w0|V0|+
l∑
i=1
wi|Vi|
= w0n+
l∑
i=1
(wi − w0)|Vi|.
Therefore, the result follows.
Corollary 3.8. The following statements hold for k, l ∈ Z+ and a graph G with minimum
degree δ ≥ 1, maximum degree ∆ and order n.
(i) If k ≤ lδ + 1 and w = (k + l − 1, k + l − 2, . . . , k − 1︸ ︷︷ ︸
l+1
), then γw(G) ≥
⌈
(k+l−1)n
∆+1
⌉
.
(ii) If k ≤ lδ and w = (k, . . . , k︸ ︷︷ ︸
l+1
), then γw(G) ≥
⌈
kn
∆
⌉
.
(iii) If k ≤ lδ + 1 and w = (k, k − 1, . . . , k − 1︸ ︷︷ ︸
l+1
), then γw(G) ≥
⌈
kn
∆+1
⌉
.
(iv) Let w = (w0, . . . , wl) with w0 ≥ · · · ≥ wl. If lδ ≥ wl, then γw(G) ≥
⌈
w0n
∆+w0
⌉
.
In the next subsections we shall show that lower bounds above are tight. Corollary 3.8
implies the following known bounds.
γ(G) ≥
⌈
n
∆+1
⌉
, γt(G) ≥
⌈
n
∆
⌉
, γ
I
(G) ≥
⌈
2n
∆+2
⌉
, γtI(G) ≥
⌈
2n
∆+1
⌉
,
γk(G) ≥
⌈
kn
∆+k
⌉
, γ×k(G) ≥
⌈
kn
∆+1
⌉
, γ{k} ≥
⌈
kn
∆+1
⌉
, γ×k,t(G) ≥
⌈
kn
∆
⌉
.
It is readily seen that γ(w0,...,wl)(G) = 1 if and only if w0 = 1, w1 = 0 and γ(G) = 1.
Next we characterize the graphs with γ(w0,...,wl)(G) = 2.
66 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
Theorem 3.9. Let w = (w0, . . . , wl) ∈ Z+ × Nl such that w0 ≥ · · · ≥ wl. For a graph
G of order at least three, γ(w0,...,wl)(G) = 2 if and only if one of the following conditions
holds.
(i) w2 = 0, γ(G) = 1 and either w0 = 2 or w0 = w1 = 1.
(ii) w0 = 1, w1 = 0 and γ(G) = 2.
(iii) w0 = 1, w1 = 1 and γt(G) = 2.
(iv) w0 = 2, w1 = 0 and γ2(G) = 2.
(v) w0 = 2, w1 = 1 and γ×2(G) = 2.
Proof. Assume first that γ(w0,...,wl)(G) = 2 and let f(V0, . . . , Vl) be a γ(w0,...,wl)(G)-
function. Notice that w0 ∈ {1, 2} and |V2| ∈ {0, 1}. If |V2| = 1, then w2 = 0 and Vi = ∅
for every i ̸= 0, 2. Hence, γ(G) = 1 and either w0 = 2 or w0 = w1 = 1. Therefore, (i)
follows.
Now we consider the case V2 = ∅. Notice that V1 is a dominating set of cardinality
two, w1 ∈ {0, 1} and Vi = ∅ for every i ̸= 0, 1.
Assume first that w0 = 1 and w1 = 0. If γ(G) = 1, then γ(w0,...,wl)(G) = 1, which
is a contradiction. Hence, γ(G) = 2 and so (ii) follows. For w0 + w1 ≥ 2 we have the
following possibilities.
If w0 = w1 = 1, then V1 is a total dominating set of cardinality two, and so γt(G) = 2.
Therefore, (iii) follows.
If w0 = 2 and w1 = 0, then V1 is a 2-dominating set of cardinality two, which implies
that γ2(G) = 2. Therefore, (iv) follows.
If w0 = 2 and w1 = 1, then V1 is a double dominating set of cardinality two, and this
implies that γ×2(G) = 2. Therefore, (v) follows.
Conversely, if one of the five conditions holds, then it is easy to check that γ(w0,...,wl)(G)
= 2, which completes the proof.
In order to establish the following result, we need to define the following parameter.
ν(w0,...,wl)(G) = max{|V0| : f(V0, . . . , Vl) is a γ(w0,...,wl)(G)-function}.
In particular, for l = 1 and a graph G of order n, we have that ν(w0,w1)(G) = n −
γ(w0,w1)(G).
Theorem 3.10. Let G be a graph of minimum degree δ and order n. The following state-
ments hold for any (w0, . . . , wl) ∈ Z+ × Nl with w0 ≥ · · · ≥ wl.
(i) If there exists i ∈ {1, . . . , l − 1} such that iδ ≥ wi, then
γ(w0,...,wl)(G) ≤ γ(w0,...,wi)(G).
(ii) If l ≥ i+ 1 ≥ w0, then
γ(w0,...,wi,0,...,0)(G) ≤ (i+ 1)γ(G).
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 67
(iii) Let k, i ∈ Z+ such that l ≥ ki, and let (w′0, w′1, . . . , w′i) ∈ Z+ × Nl. If iδ ≥ w′i and
wkj = kw
′
j for every j ∈ {0, 1, . . . , i}, then
γ(w0,...,wl)(G) ≤ kγ(w′0,...,w′i)(G).
(iv) Let k ∈ Z+ and β1, . . . , βk ∈ Z+. If lδ ≥ k + wl > k and w0 + k ≥ β1 ≥ · · · ≥
βk ≥ w1 + k, then
γ(w0+k,β1,...,βk,w1+k,...,wl+k)(G) ≤ γ(w0,...,wl)(G) + k(n− ν(w0,...,wl)(G)).
(v) If lδ ≥ wl ≥ l ≥ 2, then
γ(w0,...,wl)(G) ≤ lγ(w0−l+1,wl−l+1)(G).
(vi) If δ ≥ 1, w0 ≤ l − 1 and wl−1 ≥ 1, then
γ(w0,...,wl−2,1)(G) ≤ γ(w0,...,wl−1,0)(G).
Proof. If there exists i ∈ {1, . . . , l − 1} such that iδ ≥ wi, then for any γ(w0,...,wi)(G)-
function f(V0, . . . , Vi) we define a (w0, . . . , wl)-dominating function g(W0, . . . ,Wl) by
Wj = Vj for every j ∈ {0, . . . , i} and Wj = ∅ for every j ∈ {i + 1, . . . , l}. Hence,
γ(w0,...,wl)(G) ≤ ω(g) = ω(f) = γ(w0,...,wi)(G). Therefore, (i) follows.
Now, assume l ≥ i + 1 ≥ w0. Let S be a γ(G)-set. Let f be the function defined
by f(v) = i + 1 for every v ∈ S and f(v) = 0 for the remaining vertices. Since f
is a (w0, . . . , wi, 0 . . . , 0)-dominating function, we conclude that γ(w0,...,wi,0...,0)(G) ≤
ω(f) = (i+ 1)|S| = (i+ 1)γ(G), which implies that (ii) follows.
In order to prove (iii), assume that l ≥ ki, iδ ≥ w′i and wkj = kw′j for every
j ∈ {0, . . . , i}. Let f ′(V ′0 , . . . , V ′i ) be a γ(w′0,...,w′i)(G)-function. We construct a func-
tion f(V0, . . . , Vl) as f(v) = kf ′(v) for every v ∈ V (G). Hence, Vkj = V ′j for every
j ∈ {0, . . . , i}, while Vj = ∅ for the remaining cases. Thus, for every v ∈ Vkj with
j ∈ {0, . . . , i} we have that f(N(v)) = kf ′(N(v)) ≥ kw′j = wkj , which implies that
f is a (w0, . . . , wl)-dominating function, and so γ(w0,...,wl)(G) ≤ ω(f) = kω(f ′) =
kγ(w′0,...,w′i)(G). Therefore, (iii) follows.
Now, assume that lδ ≥ k + wl > k and w0 + k ≥ β1 ≥ · · · ≥ βk ≥ w1 + k. Let
g(W0, . . . ,Wl) be a γ(w0,...,wl)(G)-function. We construct a function f(V0, . . . , Vl+k) as
f(v) = g(v) + k for every v ∈ V (G) \ W0 and f(v) = 0 for every v ∈ W0. Hence,
Vj+k = Wj for every j ∈ {1, . . . , l}, V0 = W0 and Vj = ∅ for the remaining cases. Thus,
if v ∈ Vj+k and j ∈ {1, . . . , l}, then f(N(v)) ≥ g(N(v)) + k ≥ wj + k, and if v ∈ V0,
then f(N(v)) ≥ g(N(v)) + k ≥ w0 + k. This implies that f is a (w0 + k, β1, . . . , βk,
w1 + k, . . . , wl + k)-dominating function, and so
γ(w0+k,β1,...,βk,w1+k,...,wl+k)(G) ≤ ω(f) = ω(g) + k
l∑
j=1
|Wj |
= γ(w0,...,wl)(G) + k(n− |W0|)
≤ γ(w0,...,wl)(G) + k(n− ν(w0,...,wl)(G)).
Therefore, (iv) follows.
68 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
Furthermore, if lδ ≥ wl ≥ l ≥ 2, then by applying (iv) for k = l − 1, we deduce that
γ(w0,...,wl)(G) ≤ γ(w0−l+1,wl−l+1)(G) + (l − 1)(n− ν(w0−l+1,wl−l+1)(G))
= lγ(w0−l+1,wl−l+1)(G).
Therefore, (v) follows.
From now on, let δ ≥ 1, w0 ≤ l − 1 and wl−1 ≥ 1. Let f(V0, . . . , Vl) be a
γ(w0,...,wl−1,0)(G)-function. Assume first Vl = ∅. Since wl−1 ≥ 1, we have that f is a
(w0, . . . , wl−2, 1)-dominating function on G, which implies that (vi) follows. Assume now
that there exists v ∈ Vl. If f(N(v)) ≥ l− 1, then the function f ′, defined by f ′(v) = l− 1
and f ′(x) = f(x) for every x ∈ V (G) \ {v}, is a (w0, . . . , wl−1, 0)-dominating function
with ω(f ′) < ω(f), which is a contradiction. Hence, f(N(v)) ≤ l − 2 for every v ∈ Vl.
Since δ ≥ 1, for each vertex x ∈ Vl, we fix one vertex x′ ∈ N(x) and we form a set S
from them such that |S| ≤ |Vl|. Let g be the function defined by g(x) = f(x) + 1 for
any x ∈ S, g(y) = l − 1 for any y ∈ Vl, and g(z) = f(z) for the remaining vertices of
G. Since g(N(x)) ≥ l − 1 ≥ wi for every x ∈ S and i ∈ {0, . . . , l − 2}, g(N(y)) ≥ 1
for every y ∈ Vl−1 ∪ Vl, and g(N(z)) ≥ wi for every z ∈ Vi \ (S ∪ Vl−1 ∪ Vl) and
i ∈ {0, . . . , l − 2}, we conclude that g is a (w0, . . . , wl−2, 1)-dominating function on G.
Therefore, γ(w0,...,wl−2,1)(G) ≤ ω(g) ≤ ω(f) = γ(w0,...,wl−1,0)(G), which completes the
proof of (vi).
In the next subsections we consider several applications of Theorem 3.10 where we
show that the bounds are tight. For instance, the following particular cases will be of
interest.
Corollary 3.11. Let G be a graph of minimum degree δ, and let k, l, w2, . . . , wl ∈ Z+ with
k ≥ w2 ≥ · · · ≥ wl.
(i) If δ ≥ k and w = (k + 1, k, w2, . . . , wl), then γw(G) ≤ γ×k(G).
(ii) If δ ≥ k and w = (k, k, w2, . . . , wl), then γw(G) ≤ γ×k,t(G).
(iii) If lδ ≥ k ≥ l ≥ 2 and w = (k + 1, k, . . . , k︸ ︷︷ ︸
l+1
), then γw(G) ≤ lγ×(k−l+2)(G).
(iv) If lδ ≥ k ≥ l ≥ 2 and w = (k, k, . . . , k︸ ︷︷ ︸
l+1
), then γw(G) ≤ lγ×(k−l+1),t(G).
(v) If l ≥ k, δ ≥ 1 and w = (k, . . . , k︸ ︷︷ ︸
l+1
), then γw(G) ≤ kγt(G).
Proof. If δ ≥ k, then by Theorem 3.10(i) we conclude that (i) and (ii) follows.
If lδ ≥ k ≥ l ≥ 2, then by Theorem 3.10(v) we deduce that
γ(k + 1, k, . . . , k︸ ︷︷ ︸
l+1
)(G) ≤ lγ(k−l+2,k−l+1)(G) = lγ×(k−l+2)(G).
Hence, (iii) follows. By analogy we derive (iv), as γ(k−l+1,k−l+1)(G) = lγ×(k−l+1),t(G).
Finally, if l ≥ k and δ ≥ 1, then by Theorem 3.10(iii) we deduce that
γ(k, . . . , k︸ ︷︷ ︸
l+1
)(G) ≤ kγ(1,1)(G) = kγt(G).
Therefore, (v) follows.
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 69
3.1 Preliminary results on (2, 2, 2)-domination
Theorem 3.12. For any graph G with no isolated vertex, order n and maximum degree ∆,⌈
2n
∆
⌉
≤ γ(2,2,2)(G) ≤ 2γt(G).
Furthermore, if G has minimum degree δ ≥ 2, then
γ(2,2,2)(G) ≤ γ×2,t(G).
Proof. From Corollary 3.8 we deduce the lower bound. The upper bound γ(2,2,2)(G) ≤
2γt(G) follows by Corollary 3.11(v), while, if δ ≥ 2, then we apply Corollary 3.11(ii) to
deduce that γ(2,2,2)(G) ≤ γ×2,t(G). Therefore, the result follows.
The bounds above are tight. For instance, for the graphs G2 and G3 shown in Figure 1
we have that
⌈
2n
∆
⌉
= γ(2,2,2)(G2) = γ×2,t(G2) = 3 and γ(2,2,2)(G3) = 2γt(G3) = 8. No-
tice that every graph Gk,r belonging to the infinite family Hk constructed after Remark 3.3
satisfies the equality γ(2,2,2)(Gk,r) = γ×2,t(Gk,r) = k. Furthermore, from Theorem 3.4
we have that for any corona graph G ∼= G1⊙G2, where G1 does not have isolated vertices,
γ(2,2,2)(G) = 2γ(G) = 2γt(G).
Notice that by Theorem 3.12 we have that γ(2,2,2)(G) ≥
⌈
2n
∆
⌉
≥ 3 for every graph G
with no isolated vertex. Next we characterize all graphs with γ(2,2,2)(G) = 3. To this end,
we need to establish the following lemma.
Lemma 3.13. For a graph G, the following statements are equivalent.
(i) γ(2,2,2)(G) = γ×2,t(G).
(ii) There exists a γ(2,2,2)(G)-function f(V0, V1, V2) such that V2 = ∅.
Proof. If γ(2,2,2)(G) = γ×2,t(G), then for any γ×2,t(G)-set D, the function g(W0,W1,
W2), defined by W1 = D and W0 = V (G) \D, is a γ(2,2,2)(G)-function. Therefore, (ii)
follows.
Conversely, if there exists a γ(2,2,2)(G)-function f(V0, V1, V2) such that V2 = ∅, then
V1 is a double total dominating set of G, and so γ×2,t(G) ≤ |V1| = ω(f) = γ(2,2,2)(G).
Therefore, Theorem 3.12 leads to γ(2,2,2)(G) = γ×2,t(G).
Theorem 3.14. For a graph G, the following statements are equivalent.
(i) γ(2,2,2)(G) = 3.
(ii) γ×2,t(G) = 3.
Proof. Assume first that γ(2,2,2)(G) = 3, and let f(V0, V1, V2) be a γ(2,2,2)(G)-function.
Suppose that there exists u ∈ V2. Since f(N(u)) ≥ 2, we deduce that γ(2,2,2)(G) ≥
4, which is a contradiction. Hence, V2 = ∅ and by Lemma 3.13 we conclude that
γ×2,t(G) = 3.
Conversely, if γ×2,t(G) = 3, then G has minimum degree δ ≥ 2 and so Theorem 3.12
leads to 3 ≤
⌈
2n
∆
⌉
≤ γ(2,2,2)(G) ≤ γ×2,t(G) = 3. Therefore, γ(2,2,2)(G) = 3.
Next we consider the case of graphs with γ(2,2,2)(G) = 4.
70 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
Theorem 3.15. For a graph G, γ(2,2,2)(G) = 4 if and only if at least one of the following
conditions holds.
(i) γ×2,t(G) = 4.
(ii) γt(G) = 2 and G has minimum degree δ = 1.
(iii) γt(G) = 2 and γ×2,t(G) ≥ 4.
Proof. Assume γ(2,2,2)(G) = 4. Notice that G does not have isolated vertices. Let
f(V0, V1, V2) be a γ(2,2,2)(G)-function. If V2 = ∅, then by Lemma 3.13 we obtain that
γ×2,t(G) = γ(2,2,2)(G) = 4, and so (i) follows.
From now on, assume that |V2| ∈ {1, 2}. If |V2| = 2, then V1 = ∅ and, as a result,
V2 is a total dominating set of G, which implies that γt(G) = 2. On the other side, if
|V2| = 1, then |V1| = 2 and both vertices belonging to V1 are adjacent to the vertex of
weight two, and every v ∈ V0 satisfies N(v) ∩ V2 ̸= ∅ or V1 ⊆ N(v). This implies that
the union of V2 with a singleton subset of V1 forms a total dominating set of G, and again
γt(G) = 2. Now, if δ ≥ 2, then Theorem 3.12 leads to 4 = γ(2,2,2)(G) ≤ γ×2,t(G).
Hence, by Theorem 3.14 we conclude that either δ = 1 or γ×2,t(G) ≥ 4. Therefore, either
(ii) or (iii) holds.
Conversely, if γ×2,t(G) = 4, then G has minimum degree δ ≥ 2 and by Theorem 3.12
we have that 3 ≤ γ(2,2,2)(G) ≤ 4. Hence, by Theorem 3.14 we deduce that γ(2,2,2)(G) =
4. Finally, if γt(G) = 2, then Theorem 3.12 leads to 3 ≤ γ(2,2,2)(G) ≤ 4. Therefore, if
δ = 1 or γ×2,t(G) ≥ 4, then Theorem 3.14 leads to γ(2,2,2)(G) = 4.
Theorem 3.12 implies the next result.
Corollary 3.16. For any integer n ≥ 3,
γ(2,2,2)(Cn) = n.
In order to give the value of γ(2,2,2)(Pn), we recall the following well-known result.
Proposition 3.17 ([14]). For any integer n ≥ 3,
γt(Pn) =

n
2 if n ≡ 0 (mod 4),
n+1
2 if n ≡ 1, 3 (mod 4),
n
2 + 1 if n ≡ 2 (mod 4).
Lemma 3.18. If Pn = u1u2 . . . un is a path of order n ≥ 6, then there exists a γ(2,2,2)(Pn)-
function f such that f(un) = f(un−3) = 0 and f(un−1) = f(un−2) = 2.
Proof. Let f(V0, V1, V2) be a γ(2,2,2)(Pn)-function such that |V2| is maximum. Since un
is a leaf, f(un−1) = 2. Notice that f(un) + f(un−2) ≥ 2. Hence, we can assume that
f(un−2) = 2 and f(un) = 0. Now, if f(un−3) > 0, then we can define a (2, 2, 2)-
dominating function f ′ by f ′(un−3) = 0, f ′(un−5) = min{2, f(un−5) + f(un−3)} and
f ′(ui) = f(ui) for the remaining cases. Since ω(f ′) ≤ ω(f) = γ(2,2,2)(Pn), either f ′
is a γ(2,2,2)(Pn)-function with f ′(un−3) = 0 or f(un−3) = 0. In both cases the result
follows.
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 71
Proposition 3.19. For any integer n ≥ 3,
γ(2,2,2)(Pn) = 2γt(Pn) =

n if n ≡ 0 (mod 4),
n+ 1 if n ≡ 1, 3 (mod 4),
n+ 2 if n ≡ 2 (mod 4).
Proof. Since Theorem 3.12 leads to γ(2,2,2)(Pn) ≤ 2γt(Pn), we only need to prove
that γ(2,2,2)(Pn) ≥ 2γt(Pn). We proceed by induction on n. It is easy to check that
γ(2,2,2)(Pn) = 2γt(Pn) for n = 3, 4, 5, 6. This establishes the base case. Now, we assume
that n ≥ 7 and γ(2,2,2)(Pk) ≥ 2γt(Pk) for k < n. Let f(V0, V1, V2) be a γ(2,2,2)(Pn)-
function which satisfies Lemma 3.18, and let f ′ be the restriction of f to V (Pn−4), where
Pn = u1u2 . . . un and Pn−4 = u1u2 . . . un−4. Hence, by applying the induction hypothe-
sis,
γ(2,2,2)(Pn) = ω(f) = ω(f
′) + 4 ≥ γ(2,2,2)(Pn−4) + 4 ≥ 2γt(Pn−4) + 4 ≥ 2γt(Pn).
To conclude the proof we apply Proposition 3.17.
3.2 Preliminary results on (2, 2, 1)-domination
Theorem 3.20. For any graph G with no isolated vertex, order n and maximum degree ∆,⌈
2n+ γt(G)
∆ + 1
⌉
≤ γ(2,2,1)(G) ≤ min{3γ(G), 2γt(G)}.
Furthermore, if G has minimum degree δ ≥ 2, then
γ(2,2,1)(G) ≤ γ×2,t(G).
Proof. In order to prove the upper bound γ(2,2,1)(G) ≤ 2γt(G), we apply Remark 3.2 and
Theorem 3.12, i.e., γ(2,2,1)(G) ≤ γ(2,2,2) ≤ 2γt(G).
Now, let S be a γ(G)-set. Since G does not have isolated vertex, for each vertex
x ∈ S such that N(x) ∩ S = ∅, we fix one vertex x′ ∈ N(x) and we form a set S′
from them. Hence, S ∪ S′ is a total dominating set and |S ∪ S′| = |S| + |S′| ≤ 2γ(G).
Notice that the function g(X0, X1, X2) defined by X2 = S and X1 = S′, is a (2, 2, 1)-
dominating function on G. Thus, γ(2,2,1)(G) ≤ ω(g) = 2|S| + |S′| ≤ 3γ(G), and so
γ(2,2,1)(G) ≤ min{2γt(G), 3γ(G)}.
On the other side, if G has minimum degree δ ≥ 2, then by Corollary 3.11(ii) we have
that γ(2,2,1)(G) ≤ γ×2,t(G).
In order to prove the lower bound, let f(V0, V1, V2) be a γ(2,2,1)(G)-function. Since
V1 ∪ V2 is a total dominating set, γt(G) ≤ |V1|+ |V2|. Furthermore, from Lemma 3.7 we
have, 2n − |V2| ≤ ∆γ(2,2,1)(G), which implies that 2n + γt(G) ≤ 2n + |V1| + |V2| ≤
∆γ(2,2,1)(G)+|V1|+2|V2| = (∆+1)γ(2,2,1)(G). Therefore, the lower bound follows.
The bounds above are tight. For instance, the graph in Figure 3 satisfies γ(2,2,1)(G) =
3γ(G) = 9. Next we show that the remaining two bounds are also achieved.
Corollary 3.21. Let G be a graph with no isolated vertex, order n and maximum degree
∆. If γt(G) < n+∆+1∆+1/2 , then
γ(2,2,1)(G) = 2γt(G) or γ(2,2,1)(G) =
⌈
2n+ γt(G)
∆ + 1
⌉
.
72 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
2 2 21 1 1
3 3 3
Figure 3: This figure shows a γ(2,2,1)(G)-function and a γ(2,2,2,0)(G)-function on the same
graph.
Proof. If γ(2,2,1)(G) ̸=
⌈
2n+γt(G)
∆+1
⌉
and γ(2,2,1)(G) ̸= 2γt(G), then by Theorem 3.20 we
deduce that
⌈
2n+γt(G)
∆+1
⌉
+ 1 ≤ γ(2,2,1)(G) ≤ 2γt(G) − 1, which implies that γt(G) ≥
n+∆+1
∆+1/2 . Therefore, the result follows.
For the graphs G2 and G3 illustrated in Figure 1 we have that γt(G2) = 2 < 229 =
n+∆+1
∆+1/2 and γt(G3) = 4 <
32
7 =
n+∆+1
∆+1/2 . Notice that, γ(2,2,1)(G2) = 3 =
⌈
2n+γt(G2)
∆+1
⌉
and γ(2,2,1)(G3) = 8 = 2γt(G3).
Below we characterize the graphs with γ(2,2,1)(G) = 3.
Theorem 3.22. For a graph G with no isolated vertex, the following statements are equiv-
alent.
(i) γ(2,2,1)(G) = 3.
(ii) γ(G) = 1 or γ×2,t(G) = 3.
Proof. Assume first that γ(2,2,1)(G) = 3, and let f(V0, V1, V2) be a γ(2,2,1)(G)-function.
If V2 ̸= ∅, then V2 is a dominating set of cardinality one. Hence, γ(G) = 1. Now, if
V2 = ∅, then V1 is a double total dominating set of cardinality three. Thus, γ×2,t(G) = 3.
On the other side, by Theorem 3.20 we have that 3 ≤
⌈
2n+γt(G)
∆+1
⌉
≤ γ(2,2,1)(G) ≤
3γ(G). Hence, if γ(G) = 1, then γ(2,2,1)(G) = 3. Now, if γ×2,t(G) = 3, then G has
minimum degree δ ≥ 2 and by Theorem 3.20 we have that γ(2,2,1)(G) ≤ γ×2,t(G) = 3.
Therefore, γ(2,2,1)(G) = 3.
Next we consider the case of graphs with γ(2,2,1)(G) = 4.
Theorem 3.23. For a graph G, the following statements are equivalent.
(i) γ(2,2,1)(G) = 4.
(ii) γt(G) = γ(G) = 2 or γ×2,t(G) = 4.
Proof. Assume γ(2,2,1)(G) = 4. Notice that G does not have isolated vertices and, by
Theorem 3.20, we have that γ(G) ≥ 2. Let f(V0, V1, V2) be a γ(2,2,1)(G)-function. If V2 =
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 73
∅, then V1 is a double total dominating set of cardinality four. Hence, 3 ≤ γ×2,t(G) ≤
|V1| = 4, and Theorem 3.22 implies that γ×2,t(G) = 4.
From now on, assume that |V2| ∈ {1, 2}. If |V2| = 2, then V1 = ∅ and, as a result, V2 is
a total dominating set of G, which implies that γt(G) = γ(G) = 2. Now, if |V2| = 1, then
|V1| = 2 and both vertices belonging to V1 are adjacent to the vertex of weight two, and
every v ∈ V0 satisfies N(v)∩V2 ̸= ∅ or V1 ⊆ N(v). This implies that the union of V2 with
a singleton subset of V1 forms a total dominating set of G, and again γt(G) = γ(G) = 2.
Conversely, if γ×2,t(G) = 4, then G has minimum degree δ ≥ 2 and by Theorem 3.20
we have that 3 ≤ γ(2,2,1)(G) ≤ γ×2,t(G) = 4. Hence, by Theorem 3.22 we deduce that
γ(2,2,1)(G) = 4. Finally, if γt(G) = 2, then Theorem 3.20 leads to 3 ≤ γ(2,2,1)(G) ≤ 4.
Therefore, if γ(G) = 2 then by Theorem 3.22 we conclude that γ(2,2,1)(G) = 4.
Lemma 3.24. For any integer n ≥ 3,
γ(2,2,1)(Pn) ≤
n−
⌊
n
7
⌋
+ 1 if n ≡ 1, 2 (mod 7),
n−
⌊
n
7
⌋
otherwise.
Proof. First we show how to construct a (2, 2, 1)-dominating function f on Pn for n ∈
{2, . . . , 8}.
• n = 2: f(u1) = 2 and f(u2) = 1.
• n = 3: f(u1) = 0, f(u2) = 2 and f(u3) = 1.
• n = 4: f(u1) = f(u4) = 0 and f(u2) = f(u3) = 2.
• n = 5: f(u1) = f(u5) = 0, f(u2) = f(u4) = 2 and f(u3) = 1.
• n = 6: f(u1) = f(u6) = 0, f(u2) = f(u5) = 2 and f(u3) = f(u4) = 1.
• n = 7: f(u1) = f(u4) = f(u7) = 0, f(u2) = f(u6) = 2 and f(u3) = f(u5) = 1.
• n = 8: f(u1) = f(u4) = f(u8) = 0, f(u2) = f(u6) = f(u7) = 2 and
f(u3) = f(u5) = 1.
We now proceed to describe the construction of f for any n = 7q + r, where q ≥ 1 and
0 ≤ r ≤ 6. We partition V (Pn) = {u1, . . . , un} into q sets of cardinality 7 and for r ≥ 1
one additional set of cardinality r, in such a way that the subgraph induced by all these sets
are paths.
For any r ̸= 1, the restriction of f to each of these q paths of length 7 corresponds to
the weights associated above with P7, while for the path of length r (if any) we take the
weights associated above with Pr. The case r = 1 and q ≥ 2 is slightly different, as for the
first q − 1 paths of length 7 we take the weights associated above with P7 and for the last
8 vertices of Pn we take the weights associated above with P8.
Notice that, for n ≡ 1, 2 (mod 7), we have that γ(2,2,1)(Pn) ≤ ω(f) = 6q + r + 1 =
n−
⌊
n
7
⌋
+1, while for n ̸≡ 1, 2 (mod 7) we have γ(2,2,1)(Pn) ≤ ω(f) = 6q+r = n−
⌊
n
7
⌋
.
Therefore, the result follows.
Lemma 3.25. Let P7 = x1 . . . x7 be a subgraph of Cn and X = {x1, . . . , x7}. If f is a
(2, 2, 1)-dominating function on Cn, then
f(X) ≥ 6.
74 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
Proof. Notice that f({x1, x2, x3}) ≥ 2 and f({x4, x5, x6, x7}) ≥ 3 as f is a (2, 2, 1)-
dominating function. If f({x1, x2, x3}) ≥ 3, then we are done. Hence, we assume that
f({x1, x2, x3}) = 2. In this case, it is not difficult to deduce that f({x4, x5, x6, x7}) ≥ 4,
which implies that f(X) ≥ 6, as desired. Therefore, the proof is complete.
Lemma 3.26. For any integer n ≥ 3,
γ(2,2,1)(Cn) ≥
{
n− ⌊n7 ⌋+ 1 if n ≡ 1, 2 (mod 7),
n− ⌊n7 ⌋ otherwise.
Proof. It is easy to check that γ(2,2,1)(Cn) = n for every n ∈ {3, 4, 5, 6}. Now, let
n = 7q + r, with 0 ≤ r ≤ 6 and q ≥ 1. Let f(V0, V1, V2) be a γ(2,2,1)(Cn)-function.
If r = 0, then by Lemma 3.25 we have that ω(f) ≥ 6q = n − ⌊n7 ⌋. From now on we
assume that r ≥ 1. By Proposition 3.5 and Lemma 3.24 we deduce that γ(2,2,1)(Cn) ≤
γ(2,2,1)(Pn) < n, which implies that V2 ̸= ∅, otherwise there exists u ∈ V (Cn) = V0∪V1
such that N(u) ∩ V0 ̸= ∅ and so |N(u) ∩ V1| ≤ 1, which is a contradiction. Let x ∈ V2
and, without loss of generality, we can label the vertices of Cn in such a way that x = u1,
and u2 ∈ V1 ∪ V2 whenever r ≥ 2. We partition V (Cn) into X = {u1, . . . , ur} and
Y = {ur+1, . . . , un}. Notice that Lemma 3.25 leads to f(Y ) ≥ 6q.
Now, if r ∈ {1, 2}, then f(X) ≥ r + 1, which implies that ω(f) ≥ r + 1 + 6q =
n− ⌊n7 ⌋+ 1. Analogously, if r = 3, then f(X) ≥ r and so ω(f) ≥ r + 6q = n− ⌊
n
7 ⌋.
Finally, if r ∈ {4, 5, 6}, then as f is a (2, 2, 1)-dominating function we deduce that
f(X) ≥ r, which implies that ω(f) ≥ r + 6q = n− ⌊n7 ⌋.
The following result is a direct consequence of Proposition 3.5 and Lemmas 3.24
and 3.26.
Proposition 3.27. For any integer n ≥ 3,
γ(2,2,1)(Cn) = γ(2,2,1)(Pn) =
{
n− ⌊n7 ⌋+ 1 if n ≡ 1, 2 (mod 7),
n− ⌊n7 ⌋ otherwise.
3.3 Preliminary results on (2, 2, 0)-domination
Theorem 3.28. For any graph G with no isolated vertex, order n and maximum degree ∆,⌈
2n
∆+ 1
⌉
≤ γ(2,2,0)(G) ≤ 2γ(G).
Furthermore, if G has minimum degree δ ≥ 2, then
γ(2,2,0)(G) ≤ γ×2,t(G).
Proof. The upper bound γ(2,2,0)(G) ≤ ω(g) = 2γ(G) is derived by we applying Theo-
rem 3.10(ii) for i = 1 and l = 2. Furthermore, if G has minimum degree δ ≥ 2, then by
Corollary 3.11(ii) we have that γ(2,2,0)(G) ≤ γ×2,t(G).
Now, let f(V0, V1, V2) be a γ(2,2,0)(G)-function. From Lemma 3.7 we deduce that
2(n − |V2|)) ≤ ∆γ(2,2,0)(G), which implies that 2n ≤ 2n + |V1| ≤ (∆ + 1)γ(2,2,0)(G).
Therefore, the result follows.
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 75
Theorem 3.28 implies that, if γ(G) = n∆+1 , then γ(2,2,0)(G) =
2n
∆+1 . It is easy to
see that a graph satisfies γ(G) = n∆+1 if and only if there exists a γ(G)-set S which is a
2-packing1 and every vertex in S has degree ∆. The upper bound γ(2,2,0)(G) ≤ 2γ(G)
is achieved for the graph G shown in Figure 2, which satisfies γ(2,2,0)(G) = 2γ(G) = 6.
Furthermore, by Theorem 3.4 we have that for any corona graph G ∼= G1 ⊙G2, where G1
does not have isolated vertices, γ(2,2,0)(G) = 2γ(G).
As shown in Theorem 3.9, for a graph G, γ(2,2,0)(G) = 2 if and only if γ(G) = 1.
Now we consider the case γ(2,2,0)(G) = 3.
Theorem 3.29. For a graph G, γ(2,2,0)(G) = 3 if and only if γ×2,t(G) = γ(G) + 1 = 3.
Proof. Assume γ(2,2,0)(G) = 3. By Theorem 3.9 we have that γ(G) ≥ 2. Let f(V0, V1, V2)
be a γ(2,2,0)(G)-function. If |V2| = 1 then |V1| = 1, and as f is a (2, 2, 0)-dominating
function we deduce that N [V2] = V (G), i.e., γ(G) = 1, which is a contradiction. Thus,
V2 = ∅ and |V1| = 3. Notice that V1 is a double total dominating set and since γ(G) ≥ 2,
it follows that 3 ≤ γ(G) + 1 ≤ γ×2,t(G) ≤ |V1| = 3. Hence, γ×2,t(G) = γ(G) + 1 = 3,
as required.
Conversely, assume γ×2,t(G) = γ(G) + 1 = 3. Since G has minimum degree at least
two, Theorem 3.28 leads to 2 ≤ γ(2,2,0)(G) ≤ γ×2,t(G) = 3, and so Theorem 3.9 implies
that γ(2,2,0)(G) = 3, which completes the proof.
Theorem 3.30. For a graph G, γ(2,2,0)(G) = 4 if and only if one of the following condi-
tions holds.
(i) G ∼= K1 ∪G1, where G1 is a graph with γ(G1) = 1.
(ii) γ×2,t(G) = 4.
(iii) γ(G) = 2 and G has minimum degree one.
(iv) γ(G) = 2 and γ×2,t(G) ≥ 4.
Proof. If K1 is a component of G, then by Theorem 3.9 we conclude that γ(2,2,0)(G) = 4
if and only if G ∼= K1 ∪G1, where G1 is a graph with γ(G1) = 1.
From now on, we consider the case where G is a graph with no isolated vertex. Assume
γ(2,2,0)(G) = 4 and let f(V0, V1, V2) be a γ(2,2,0)(G)-function. If V2 = ∅, then V1 is a
double total dominating set of G. In this case, G has minimum degree δ ≥ 2 and by
Theorem 3.28 we have that γ×2,t(G) ≤ |V1| = 4 = γ(2,2,0)(G) ≤ γ×2,t(G). Hence (ii)
follows.
Now, assume that |V2| ∈ {1, 2}. If |V2| = 2, then V1 = ∅, and so γ(G) ≤ 2. Now, if
|V2| = 1, then |V1| = 2 and both vertices belonging V1 are adjacent to the vertex of weight
two, and every v ∈ V0 satisfies N(v) ∩ V2 ̸= ∅ or V1 ⊆ N(v). This implies that the union
of V2 with a singleton subset of V1 forms a dominating set of G, and again γ(G) ≤ 2. Thus,
from Theorem 3.9 we deduce that γ(G) = 2. Furthermore, if δ ≥ 2, then by Theorem 3.28
we have that γ×2,t(G) ≥ γ(2,2,0) = 4. Therefore, either (iii) or (iv) holds.
Conversely, if γ×2,t(G) = 4, then Theorem 3.28 leads to 2 ≤ γ(2,2,0) ≤ γ×2,t(G) = 4.
Hence, by Theorems 3.9 and 3.29 we deduce that γ(2,2,0)(G) = 4. Analogously, if γ(G) =
2 and δ ≥ 1, then Theorem 3.28 leads to 2 ≤ γ(2,2,0) ≤ 2γ(G) = 4. Thus, by Theorem 3.9
we have that 3 ≤ γ(2,2,0) ≤ 4. In particular, if δ = 1 or γ×2,t(G) ≥ 4, then Theorem 3.29
leads to γ(2,2,0)(G) = 4, which completes the proof.
1A set S ⊆ V (G) is a 2-packing if N [u] ∩N [v] = ∅ for every pair of different vertices u, v ∈ S.
76 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
Lemma 3.31. For a graph G, the following statements are equivalent.
(i) γ(2,2,0)(G) = 2γ(G).
(ii) There exists a γ(2,2,0)(G)-function f(V0, V1, V2) such that V1 = ∅.
Proof. First, we assume that γ(2,2,0)(G) = 2γ(G) and let D be a γ(G)-set. Hence, the
function f(V0, V1, V2), defined by V2 = D and V0 = V (G) \D, is a γ(2,2,0)(G)-function
which satisfies (ii), as desired.
Finally, we assume that there exists a γ(2,2,0)(G)-function f(V0, V1, V2) such that V1 =
∅. This implies that V2 is a dominating set of G. Hence, γ(2,2,0)(G) ≤ 2γ(G) ≤ 2|V2| =
γ(2,2,0)(G), and the desired equality holds, which completes the proof.
The following result provides the (2, 2, 0)-domination number of paths and cycles.
Proposition 3.32. For any integer n ≥ 3,
γ(2,2,0)(Pn) = γ(2,2,0)(Cn) = 2
⌈n
3
⌉
.
Proof. We first prove that γ(2,2,0)(Cn) ≥ 2
⌈
n
3
⌉
. Let f(V0, V1, V2) be a γ(2,2,0)(Cn)-
function. If V1 = ∅, then by Lemma 3.31 it follows that γ(2,2,0)(Cn) = 2γ(Cn) = 2
⌈
n
3
⌉
.
If V1 ̸= ∅, then 1 + 2|V2| ≤ |V1|+ 2|V2| = γ(2,2,0)(Cn) ≤ 2γ(Cn) = 2
⌈
n
3
⌉
, which leads
to |V2| ≤
⌈
n
3
⌉
− 1. By Lemma 3.7 we have that γ(2,2,0)(Cn) ≥ n− |V2| ≥ n−
⌈
n
3
⌉
+1 ≥
2
⌈
n
3
⌉
, as desired.
Therefore, by the inequality above, Proposition 3.5 and Theorem 3.28 we deduce that
2⌈n3 ⌉ ≤ γ(2,2,0)(Cn) ≤ γ(2,2,0)(Pn) ≤ 2γ(Pn) = 2⌈
n
3 ⌉. Thus, we have equalities in the
inequality chain above, which implies that the result follows.
3.4 Preliminary results on (2, 1, 0)-domination
Given a graph G, we use the notation L(G) and S(G) for the sets of leaves and support
vertices, respectively.
Theorem 3.33. For any graph G with no isolated vertex, order n and maximum degree ∆,⌈
2n
∆+ 1
⌉
≤ γ(2,1,0)(G) ≤ min{γ×2(G)− |L(G)|+ |S(G)|, 2γ(G)}.
Proof. If f(V0, V1, V2) is a γ(2,1,0)(G)-function, then from Lemma 3.7 we conclude that
2n−|V1|−2|V2| ≤ ∆γ(2,1,0)(G). Hence, 2n ≤ ∆γ(2,1,0)(G)+ω(f) = (∆+1)γ(2,1,0)(G).
Therefore, the lower bound follows.
Let D be a γ×2(G)-set. Notice that S(G) ∪ L(G) ⊆ D. Since |N [v] ∩ D| ≥ 2 for
every v ∈ V (G), the function g(V0, V1, V2) defined by V1 = D \ (L(G) ∪ S(G)) and
V2 = S(G), is a (2, 1, 0)-dominating function. Hence, γ(2,1,0)(G) ≤ ω(g) = γ×2(G) −
|L(G)|+ |S(G)|.
By Remark 3.2, γ(2,1,0)(G) ≤ γ(2,2,0)(G), hence the upper bound γ(2,1,0)(G) ≤
2γ(G) is derived from Theorem 3.28. Therefore, γ(2,1,0)(G) ≤ min{γ×2(G)− |L(G)|+
|S(G)|, 2γ(G)}.
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 77
The bounds above are tight. For instance, for the graph G1 shown in Figure 1 we have
that γ(2,1,0)(G1) =
⌈
2n
∆+1
⌉
= γ×2(G1) = 2γ(G1) = 4. As an example of graph of
minimum degree one where γ(2,1,0)(G) = γ×2(G) − |L(G)| + |S(G)| we take the graph
G obtained from a star graph K1,r, r ≥ 3, by subdividing one edge just once. In such a
case, γ(2,1,0)(G) = 4 = γ×2(G)− |L(G)|+ |S(G)|. Another example is the graph shown
in Figure 2 which satisfies γ(2,1,0)(G) = γ×2(G)− |L(G)|+ |S(G)| = 6.
Notice that γ(2,1,0)(G) ≥
⌈
2n
∆+1
⌉
≥ 2. As shown in Theorem 3.9, γ(2,1,0)(G) = 2 if
and only if γ(G) = 1. Next we characterize the graph satisfying γ(2,1,0)(G) = 3.
Theorem 3.34. For a graph G, γ(2,1,0)(G) = 3 if and only if γ×2(G) = γ(G) + 1 = 3.
Proof. Assume γ(2,1,0)(G) = 3. By Theorem 3.9 we have that γ(G) ≥ 2. Let f(V0, V1, V2)
be a γ(2,1,0)(G)-function. If |V2| = 1 then N [V2] = V (G), i.e., γ(G) = 1, which is a con-
tradiction. Thus, V2 = ∅ and |V1| = 3, which implies that V1 is a double dominating set.
Hence, 3 ≤ γ(G) + 1 ≤ γ×2(G) ≤ |V1| = 3. Therefore, γ×2(G) = γ(G) + 1 = 3.
Conversely, assume γ×2(G) = γ(G) + 1 = 3. Notice that G has minimum degree
δ ≥ 1 and so by Theorems 3.9 and 3.33 we have that 3 ≤ γ(2,1,0)(G) ≤ γ×2(G) = 3,
which implies that γ(2,1,0)(G) = 3.
Next we consider the case of graphs with γ(2,1,0)(G) = 4.
Theorem 3.35. For a graph G, γ(2,1,0)(G) = 4 if and only if one of the following condi-
tions is satisfied.
(i) G ∼= K1 ∪G1, where G1 is a graph with γ(G1) = 1.
(ii) γ×2(G) = 4.
(iii) γ(G) = 2 and γ×2(G) ≥ 4.
Proof. If K1 is a component of G, then by Theorem 3.9 we conclude that γ(2,1,0)(G) = 4
if and only if G ∼= K1 ∪G1, where G1 is a graph with γ(G1) = 1.
From now on, we consider the case where G is a graph with no isolated vertex. Assume
γ(2,1,0)(G) = 4. By Theorem 3.33 we deduce that γ×2(G) ≥ 4 and γ(G) ≥ 2. Let
f(V0, V1, V2) be a γ(2,1,0)(G)-function. If V2 = ∅, then V1 is a double dominating set of
G, which implies that γ×2(G) ≤ |V1| = 4. Hence, (ii) follows. From now on, assume
|V2| ∈ {1, 2}. If |V2| = 2, then V1 = ∅ and so, V2 is a dominating set of G, which implies
that γ(G) = 2. If |V2| = 1, then for every v ∈ V1 we have that V2 ∪ {v} is a dominating
set of G. Hence, γ(G) = 2. Therefore, (iii) follows.
Conversely, if (ii) or (iii) holds, then by Theorems 3.33 we have that 2 ≤ γ(2,1,0)(G) ≤
4. Therefore, by Theorems 3.9 and 3.34 we deduce that γ(2,1,0)(G) = 4, which completes
the proof.
The formulas on the {k}-dominating number of cycles and paths were obtained in [17].
We present here the particular case of k = 2, as γ{2}(G) = γ(2,1,0)(G).
Proposition 3.36 ([17]). For any integer n ≥ 3,
γ{2}(Cn) =
⌈
2n
3
⌉
and γ{2}(Pn) = 2
⌈n
3
⌉
.
78 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
3.5 Preliminary results on (2, 2, 2, 0)-domination
The following result is a direct consequence of Theorem 3.10(i), (ii) and (vi).
Corollary 3.37. For any graph G with no isolated vertex,
γ(2,2,1)(G) ≤ γ(2,2,2,0)(G) ≤ min{3γ(G), γ(2,2,2)(G)}.
The bounds above are tight. For instance, every graph Gk,r belonging to the in-
finite family Hk constructed after Remark 3.3 satisfies the equalities γ(2,2,1)(Gk,r) =
γ(2,2,2)(Gk,r) = γ(2,2,2,0)(Gk,r) = k. In contrast, the graph shown in Figure 2 satis-
fies γ(2,2,1)(G) = 6 < 7 = γ(2,2,2,0)(G) < 8 = γ(2,2,2)(G). Moreover, Figure 3 illustrates
a graph G with γ(2,2,1)(G) = γ(2,2,2,0)(G) = 3γ(G) = 9.
In order to characterize the graphs with γ(2,2,2,0)(G) ∈ {3, 4}, we need to establish the
following lemma.
Lemma 3.38. For a graph G, the following statements are equivalent.
(i) γ(2,2,2,0)(G) = γ(2,2,2)(G).
(ii) There exists a γ(2,2,2,0)(G)-function f(V0, V1, V2, V3) such that V3 = ∅.
Proof. If γ(2,2,2,0)(G) = γ(2,2,2)(G), then for any γ(2,2,2)(G)-function f(V0, V1, V2), there
exists a γ(2,2,2,0)(G)-function g(W0,W1,W2,W3) defined by W0 = V0, W1 = V1, W2 =
V2 and W3 = ∅. Therefore, (i) implies (ii).
Conversely, if there exists a γ(2,2,2,0)(G)-function f(V0, V1, V2, V3) such that V3 = ∅,
then the function g(W0,W1,W2), defined by W0 = V0, W1 = V1 and W2 = V2, is a
(2, 2, 2)-dominating function on G, and so γ(2,2,2)(G) ≤ ω(g) = ω(f) = γ(2,2,2,0)(G).
Therefore, Corollary 3.37 leads to γ(2,2,2,0)(G) = γ(2,2,2)(G), which completes the proof.
Theorem 3.39. For a graph G, the following statements are equivalent.
(i) γ(2,2,2,0)(G) = 3.
(ii) γ(G) = 1 or γ×2,t(G) = 3.
Proof. Assume first that γ(2,2,2,0)(G) = 3, and let f(V0, V1, V2, V3) be a γ(2,2,2,0)(G)-
function. Notice that |V3| ∈ {0, 1}. If |V3| = 1, then V1 ∪ V2 = ∅, which implies that V3
is a dominating set of cardinality one. Hence, γ(G) = 1.
If V3 = ∅, then by Lemma 3.38 we have that γ(2,2,2)(G) = γ(2,2,2,0)(G) = 3, and by
Theorem 3.14 we deduce that γ×2,t(G) = 3.
Conversely, if γ(G) = 1, then Corollary 3.37 leads to 3 ≤ γ(2,2,2,0)(G) ≤ 3γ(G) = 3.
Moreover, if γ×2,t(G) = 3, then G has minimum degree δ ≥ 2 and so Theorem 3.10(i)
leads to 3 ≤ γ(2,2,2,0)(G) ≤ γ(2,2,2)(G) ≤ γ×2,t(G) = 3. Therefore, γ(2,2,2,0)(G) = 3.
Theorem 3.40. For a graph G, γ(2,2,2,0)(G) = 4 if and only if at least one of the following
conditions holds.
(i) γ×2,t(G) = 4.
(ii) γ(G) = γt(G) = 2 and G has minimum degree δ = 1.
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 79
(iii) γ(G) = γt(G) = 2 and γ×2,t(G) ≥ 4.
Proof. Assume γ(2,2,2,0)(G) = 4. Let f(V0, V1, V2, V3) be a γ(2,2,2,0)(G)-function. Hence,
|V3| ∈ {0, 1}. If |V3| = 1, then V3 is a dominating set of cardinality one. Hence, γ(G) = 1,
which is a contradiction with Theorem 3.39. Hence, V3 = ∅, and so, Lemma 3.38 leads to
γ(2,2,2)(G) = γ(2,2,2,0)(G) = 4. Thus, by Theorems 3.15 and 3.39 we deduce (i) – (iii).
Conversely, if conditions (i) – (iii) hold, then by Theorem 3.14 we have that
γ(2,2,2)(G) = 4. Corollary 3.37 leads to 3 ≤ γ(2,2,2,0)(G) ≤ γ(2,2,2)(G) = 4. No-
tice that if δ ≥ 2, then γ(G) ≥ 2 and γ×2,t(G) ≥ 4. Hence, Theorem 3.39 leads to
γ(2,2,2,0)(G) = 4.
Proposition 3.41. For any integer n ≥ 3,
γ(2,2,2,0)(Cn) = n.
Proof. By Corollaries 3.16 and 3.37 we have that γ(2,2,2,0)(Cn) ≤ γ(2,2,2)(Cn) = n.
We only need to prove that γ(2,2,2,0)(Cn) ≥ n. Let f(V0, V1, V2, V3) be a γ(2,2,2,0)(G)-
function such that |V3| is minimum. If V3 = ∅, then by Lemma 3.38 and Corollary 3.16
we conclude that γ(2,2,2,0)(Cn) = n. Assume V3 ̸= ∅. If v ∈ V3, then N(v) ⊆ V0 as
otherwise, by choosing one vertex u ∈ N(v) \ V0, the function f ′ defined by f ′(v) = 2,
f ′(u) = min{2, f(u) + 1} and f ′(x) = f(x) for the remaining vertices, is a (2, 2, 2, 0)-
dominating function with ω(f ′) ≤ ω(f) and |V ′3 | < |V3|, which is a contradiction. Hence,∑
x∈V3 f(N [x]) = 3|V3|. Now, we observe that
2
∑
x∈V (Cn)\N [V3]
f(x) ≥
∑
x∈V (Cn)\N [V3]
 ∑
u∈N(x)
f(u)
 ≥ 2(n− 3|V3|).
Therefore,
γ(2,2,2,0)(Cn) = ω(f) =
∑
x∈V3
f(N [x]) +
∑
x∈V (Cn)\N [V3]
f(x)
≥ 3|V3|+ (n− 3|V3|) = n,
and the result follows.
Proposition 3.42. For any integer n ≥ 3,
γ(2,2,2,0)(Pn) =
{
6 if n = 5,
n otherwise.
Proof. It is easy to check that γ(2,2,2,0)(Pn) = n for n = 3, 4, 6, 7, 8, and also
γ(2,2,2,0)(P5) = 6. From now on, assume n ≥ 9. By Propositions 3.5 and 3.41 we have that
n = γ(2,2,2,0)(Cn) ≤ γ(2,2,2,0)(Pn). Hence, we only need to prove that γ(2,2,2,0)(Pn) ≤ n.
To this end, we proceed to construct a (2, 2, 2, 0)-dominating function f(V0, V1, V2, V3) on
Pn = v1v2 . . . vn such that ω(f) = n.
• If n ≡ 0 (mod 3), then we set V3 =
⋃n/3
i=1{v3i−1} and V0 = V (G) \ V3.
• If n ≡ 1 (mod 3), then we set V3 =
⋃(n−4)/3
i=1 {v3i−1}, V2 = {vn−2, vn−1} and
V0 = V (G) \ (V2 ∪ V3).
80 Ars Math. Contemp. 22 (2022) #P1.04 / 57–81
• If n ≡ 2 (mod 3), then we set V3 =
⋃(n−8)/3
i=1 {v3i−1}, V2 = {vn−6, vn−5, vn−2,
vn−1} and V1 = ∅.
Notice that in the three cases above, f is a (2, 2, 2, 0)-dominating function of weight
ω(f) = n, as required. Therefore, the proof is complete.
ORCID iDs
Abel Cabrera Martı́nez https://orcid.org/0000-0003-2806-4842
Alejandro Estrada-Moreno https://orcid.org/0000-0001-9767-2177
Juan Alberto Rodrı́guez-Velázquez https://orcid.org/0000-0002-9082-7647
References
[1] H. Abdollahzadeh Ahangar, M. Chellali, S. M. Sheikholeslami and J. C. Valenzuela-Tripodoro,
Total Roman {2}-dominating functions in graphs, Discuss. Math. Graph Theory (2020), doi:
10.7151/dmgt.2316, in press.
[2] D. W. Bange, A. E. Barkauskas, L. H. Host and P. J. Slater, Generalized domination and ef-
ficient domination in graphs, Discrete Math. 159 (1996), 1–11, doi:10.1016/0012-365x(95)
00094-d.
[3] B. Brešar, M. A. Henning and S. Klavžar, On integer domination in graphs and Vizing-like
problems, Taiwanese J. Math. 10 (2006), 1317–1328, doi:10.11650/twjm/1500557305.
[4] S. Cabrera Garcı́a, A. Cabrera Martı́nez, F. A. Hernández Mira and I. G. Yero, Total Roman
{2}-domination in graphs, Quaest. Math. 44 (2021), 411–434, doi:10.2989/16073606.2019.
1695230.
[5] A. Cabrera Martı́nez, S. Cabrera Garcı́a and J. A. Rodrı́guez-Velázquez, Double domination in
lexicographic product graphs, Discrete Appl. Math. 284 (2020), 290–300, doi:10.1016/j.dam.
2020.03.045.
[6] M. Chellali, T. W. Haynes, S. T. Hedetniemi and A. A. McRae, Roman {2}-domination, Dis-
crete Appl. Math. 204 (2016), 22–28, doi:10.1016/j.dam.2015.11.013.
[7] G. S. Domke, S. T. Hedetniemi, R. C. Laskar and G. Fricke, Relationships between integer
and fractional parameters of graphs, in: Y. Alavi, G. Chartrand, O. R. Oellermann and A. J.
Schwenk (eds.), Graph Theory, Combinatorics, and Applications, Volume 1, Wiley, New York,
A Wiley-Interscience Publication, pp. 371–387, 1991, proceedings of the Sixth Quadrennial
International Conference on the Theory and Applications of Graphs held at Western Michigan
University, Kalamazoo, Michigan, May 30–June 3, 1988.
[8] J. F. Fink and M. S. Jacobson, n-domination in graphs, in: Y. Alavi, G. Chartrand, D. R. Lick
and C. E. Wall (eds.), Graph Theory with Applications to Algorithms and Computer Science,
John Wiley & Sons, New York, A Wiley-Interscience Publication, 1985 pp. 283–300.
[9] F. Harary and T. W. Haynes, Double domination in graphs, Ars Combin. 55 (2000), 201–213.
[10] T. W. Haynes, S. T. Hedetniemi and P. J. Slater (eds.), Domination in Graphs: Advanced Topics,
volume 209 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker,
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,
New York, 1998, doi:10.1201/9781482246582.
[12] M. A. Henning and A. P. Kazemi, k-tuple total domination in graphs, Discrete Appl. Math. 158
(2010), 1006–1011, doi:10.1016/j.dam.2010.01.009.
A. Cabrera Martı́nez et al.: From Italian domination in lexicographic product graphs to . . . 81
[13] M. A. Henning and W. F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217
(2017), 557–564, doi:10.1016/j.dam.2016.09.035.
[14] M. A. Henning and A. Yeo, Total Domination in Graphs, Springer Monographs in Mathemat-
ics, Springer, New York, 2013, doi:10.1007/978-1-4614-6525-6.
[15] X. Hou and Y. Lu, On the {k}-domination number of Cartesian products of graphs, Discrete
Math. 309 (2009), 3413–3419, doi:10.1016/j.disc.2008.07.030.
[16] W. F. Klostermeyer and G. MacGillivray, Roman, Italian, and 2-domination, J. Combin. Math.
Combin. Comput. 108 (2019), 125–146.
[17] C.-M. Lee and M.-S. Chang, Variations of Y -dominating functions on graphs, Discrete Math.
308 (2008), 4185–4204, doi:10.1016/j.disc.2007.08.080.