ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 233–241
https://doi.org/10.26493/1855-3974.2284.aeb
(Also available at http://amc-journal.eu)
Closed formulas for the total Roman domination
number of lexicographic product graphs
Abel Cabrera Martı́nez , 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 19 March 2020, accepted 6 January 2021, published online 6 November 2021
Abstract
Let G be a graph with no isolated vertex and f : V (G) → {0, 1, 2} a function. Let
Vi = {x ∈ V (G) : f(x) = i} for every i ∈ {0, 1, 2}. We say that f is a total Roman
dominating function on G if every vertex in V0 is adjacent to at least one vertex in V2
and the subgraph induced by V1 ∪ V2 has no isolated vertex. The weight of f is ω(f) =∑
v∈V (G) f(v). The minimum weight among all total Roman dominating functions onG is
the total Roman domination number of G, denoted by γtR(G). It is known that the general
problem of computing γtR(G) is NP-hard. In this paper, we show that if G is a graph with
no isolated vertex and H is a nontrivial graph, then the total Roman domination number of
the lexicographic product graph G ◦H is given by
γtR(G ◦H) =
{
2γt(G) if γ(H) ≥ 2,
ξ(G) if γ(H) = 1,
where γ(H) is the domination number of H , γt(G) is the total domination number of G
and ξ(G) is a domination parameter defined on G.
Keywords: Total Roman domination, total domination, lexicographic product graph.
Math. Subj. Class. (2020): 05C69, 05C76
1 Introduction
Let G be a graph with no isolated vertex and f : V (G) → {0, 1, 2} a function. Let Vi =
{x ∈ V (G) : f(x) = i} for every i ∈ {0, 1, 2}. We will identify f with the partition of
E-mail addresses: abel.cabrera@urv.cat (Abel Cabrera Martı́nez), juanalberto.rodriguez@urv.cat (Juan
Alberto Rodrı́guez-Velázquez)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
234 Ars Math. Contemp. 20 (2021) 233–241
V (G) induced by f and write f(V0, V1, V2). The weight of f is defined to be
ω(f) = f(V (G)) =
∑
v∈V (G)
f(v) = |V1|+ 2|V2|.
A function f(V0, V1, V2) is said to be total Roman dominating function onG if every vertex
in V0 is adjacent to at least one vertex in V2 and the subgraph induced by V1 ∪ V2 has no
isolated vertex [17]. The minimum weight among all total Roman dominating functions
on G is the total Roman domination number of G, denoted by γtR(G). In this article, we
continue the study initiated in [5] on the total Roman domination number of lexicographic
product graphs. In particular, we give closed formulas for the total Roman domination
number of lexicographic product graphs.
Let G and H be two graphs. The lexicographic product of 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.
For a basic introduction to the lexicographic product of two graphs we suggest the
books [7, 12]. One of the main problems in the study of G ◦ H consists of finding exact
values or tight bounds for specific parameters of these graphs and express them in terms
of known invariants of G and H . In particular, we cite the following works on domination
theory of lexicographic product graphs: (total) domination [14, 18, 19, 21], Roman domi-
nation [14], weak Roman domination [20], rainbow domination [15], super domination [6],
doubly connected domination [2], secure domination [13], double domination [3] and total
Roman domination [5].
We assume that the reader is familiar with the basic concepts and terminology of domi-
nation in graph. If this is not the case, we suggest the textbooks [8, 9, 11]. In particular, we
use the standard notation γ(G) and γt(G) for the domination number and the total domi-
nation number of a graph G, respectively. Throughout the paper, N(v) will denote the set
of neighbours or open neighbourhood of v in G. The closed neighbourhood of v, denoted
by N [v], equals N(v) ∪ {v}. A vertex v ∈ V (G) such that N [v] = V (G) is said to be a
universal vertex. For the remainder of the paper, definitions will be introduced whenever a
concept is needed.
2 The case where γ(H) ≥ 2
The next theorem merges two results obtained in [14] and [21].
Theorem 2.1 ([14] and [21]). For any graph G with no isolated vertex and any nontrivial
graph H ,
γ(G ◦H) =
{
γ(G), if γ(H) = 1,
γt(G), if γ(H) ≥ 2.
Below we present two theorems that complete the tools we need to deduce our first
result.
Theorem 2.2 ([1]). For any graph G with no isolated vertex,
2γ(G) ≤ γtR(G) ≤ min{2γt(G), 3γ(G)}.
A. Cabrera Martı́nez and J. A. Rodrı́guez-Velázquez: Closed formulas for the total Roman . . . 235
Theorem 2.3 ([4]). For any graph G with no isolated vertex and any nontrivial graph H ,
γt(G ◦H) = γt(G).
From the results above we deduce the following main theorem.
Theorem 2.4. For any graph G with no isolated vertex and any graph H with γ(H) ≥ 2,
γtR(G ◦H) = 2γt(G).
Proof. The result immediately follows by applying Theorems 2.1, 2.3 and 2.2, in this order,
i.e., 2γt(G) = 2γ(G ◦H) ≤ γtR(G ◦H) ≤ 2γt(G ◦H) = 2γt(G).
Notice that, since the general optimization problem of finding the total domination
number of a graph is NP-hard [16], by Theorem 2.4 we can conclude that the problem of
finding the total Roman domination number is NP-hard. Even so, we would like to point
out that there are several families of graphs for which the total domination number can be
found in polynomial time [10].
3 The case where γ(H) = 1
The following two lemmas are the main tools in this section.
Lemma 3.1. Let G be a graph with no isolated vertex. For any nontrivial graph H with
γ(H) = 1, there exists a γtR(G ◦H)-function f satisfying the following two conditions.
(i) f(V (Hu)) ≤ 2 for every u ∈ V (G).
(ii) If f(V (Hu)) = 2, then f(u, v) = 2 for some universal vertex v of H .
Proof. Given a TRDF f on G ◦H , we define the set Rf = {x ∈ V (G) : f(V (Hx)) ≥ 3}.
Let f be a γtR(G◦H)-function such that |Rf | is minimum among all γtR(G◦H)-functions.
Let v ∈ V (H) be a universal vertex and suppose that there exists u ∈ Rf . We differentiate
the following two cases.
Case 1. There exists u′ ∈ N(u) such that f(V (Hu′)) ≥ 1. Let f ′ be the function defined
by f ′(V (Hu)) = f ′(u, v) = 2 and f ′(x, y) = f(x, y) for every x ∈ V (G) \ {u}. It is
readily seen that f ′ is a γtR(G ◦H)-function with |Rf ′ | < |Rf |, which is a contradiction.
Case 2. f(N(u) × V (H)) = 0. In this case, we choose a vertex u′ ∈ N(u) and define a
function f ′ as f ′(V (Hu′)) = f ′(u′, v) = 1, f ′(V (Hu)) = f ′(u, v) = 2 and f ′(x, y) =
f(x, y) for every x ∈ V (G) \ {u, u′}. As in Case 1, f ′ is a γtR(G ◦ H)-function with
|Rf ′ | < |Rf |, which is a contradiction.
According to the two cases above, (i) follows. Now, for any γtR(G ◦ H)-function
f(V0, V1, V2) satisfying (i), we define R′f = {x ∈ V (G) : f(V (Hx)) = 2 and V (Hx) ∩
V2 = ∅}. Let g(V ′0 , V ′1 , V ′2) be a γtR(G◦H)-function such that |R′g| is minimum among all
γtR(G ◦H)-functions satisfying (i). Suppose that there exists u ∈ R′g . If there exists u′ ∈
N(u) such that, g(V (Hu′)) = 2, then the function g′ defined by g′(V (Hu)) = g′(u, v) =
1 and g′(x, y) = g(x, y) for every x ∈ V (G) \ {u}, is a TRDF on G ◦ H of weight
ω(g′) < ω(g) = γtR(G ◦H), which is a contradiction. Hence, g(N(u)× V (H)) ≤ 1 and
we can differentiate the following two cases.
236 Ars Math. Contemp. 20 (2021) 233–241
Case 1′. There exists u′ ∈ N(u) such that g(V (Hu′)) = 1. In this case, we define a
function g′ by g′(V (Hu)) = g′(u, v) = 2 and g′(x, y) = g(x, y) for every x ∈ V (G) \
{u}. Notice that g′ is a γtR(G ◦ H)-function satisfying (i) and |R′g′ | < |R′g|, which is a
contradiction.
Case 2′. g(N(u) × V (H)) = 0. We fix u′ ∈ N(u). Notice that there exists u′′ ∈
N(u′)\{u}, with V (Hu′′)∩V ′2 ̸= ∅. Hence, we can define a function g′ as g′(V (Hu′)) =
g′(u′, v) = g′(V (Hu)) = g
′(u, v) = 1 and g′(x, y) = g(x, y) for every x ∈ V (G) \
{u, u′}. As in Case 1′, g′ is a γtR(G ◦H)-function satisfying (i) and |R′g′ | < |R′g|, which
is a contradiction.
According to the two cases above, R′g = ∅, and so there exists a γtR(G ◦H)-function
h defined as h(V (Hu)) = h(u, v) = 2 whenever g(V (Hu)) = 2 and h(V (Hu)) =
g(V (Hu)) otherwise. Therefore, h satisfies (i) and (ii).
Lemma 3.2. Let G be a graph with no isolated vertex and H a nontrivial graph with
γ(H) = 1. Let f(V0, V1, V2) be a γtR(G ◦H)-function, A = {x ∈ V (G) : V (Hx)∩V1 ̸=
∅} and B = {x ∈ V (G) : V (Hx) ∩ V2 ̸= ∅}. If f satisfies Lemma 3.1, then B is a
dominating set and A ∪B is a total dominating set of G.
Proof. Let f(V0, V1, V2) be a γtR(G ◦ H)-function which satisfies Lemma 3.1. Let C =
V (G) \ (A∪B). Obviously, if x ∈ C, then V (Hx) ⊆ V0, which implies that x is adjacent
to some vertex in B and, since H is a nontrivial graph and f satisfies Lemma 3.1, if x ∈ A,
then there exists y ∈ V (H) such that (x, y) ∈ V0, and so x is adjacent to some vertex in B.
Hence, B is a dominating set of G. Now, since the subgraph of G ◦H induced by V1 ∪ V2
does not have isolated vertices, the subgraph of G induced by A∪B does not have isolated
vertices, which implies that A ∪B is total dominating set of G.
For any graphG, let D(G) be the set of dominating sets ofG, and Dt(G) the set of total
dominating sets of G. We now proceed to introduce our main tool, which is the following
domination parameter.
ξ(G) = min{|A|+ 2|B| : B ∈ D(G) and A ∪B ∈ Dt(G)}.
We say that an ordered pair (A,B) of subsets of V (G) is a ξ(G)-pair if B ∈ D(G),
A ∪B ∈ Dt(G) and ξ(G) = |A|+ 2|B|.
Theorem 3.3. For any graph G with no isolated vertex and any nontrivial graph H with
γ(H) = 1,
γtR(G ◦H) = ξ(G).
Proof. Let v be a universal vertex ofH . From any ξ(G)-pair (A,B) we define the function
f(V0, V1, V2) as V2 = B×{v}, V1 = A×{v} and V0 = V (G◦H)\(V1∪V2). Since V2 is a
dominating set ofG◦H and V1∪V2 is a total dominating set ofG◦H , we can conclude that
f is a TRDF onG◦H . Therefore, γtR(G◦H) ≤ ω(f) = |V1|+2|V2| = |A|+2|B| = ξ(G).
Now, let f ′(V ′0 , V
′
1 , V
′
2) be a γtR(G ◦ H)-function which satisfies Lemma 3.1. Let
A = {x ∈ V (G) : f ′(V (Hx)) = 1} and B = {x ∈ V (G) : f ′(V (Hx)) = 2}. By
Lemma 3.2, B is a dominating set of G and A∪B is a total dominating set, which implies
that ξ(G) ≤ |A|+ 2|B| = |V ′1 |+ 2|V ′2 | = γtR(G ◦H). Therefore, the result follows.
A. Cabrera Martı́nez and J. A. Rodrı́guez-Velázquez: Closed formulas for the total Roman . . . 237
a
db c e
f
2 1 2 1 2
a
db c e
f
2 2 2 2
Figure 1: The labels correspond to two different γtR(G)-functions f1(V0, V1, V2), on the
left, and f2(W0,W1,W2), on the right. In this case, γtR(G) = 2γt(G) = 8, V2 = {a, d, f}
is a γ(G)-set and W2 = {a, b, e, f} is the only γt(G)-set.
Let G be the graph shown in Figure 1 and H a nontrivial graph with γ(H) = 1. Notice
that γtR(G ◦ H) = ξ(G) = γtR(G) = 8, where f1(V0, V1, V2) and f2(W0,W1,W2)
are γtR(G)-functions for V1 = {b, e}, V2 = {a, d, f}, W1 = ∅, W2 = {a, b, e, f}.
Furthermore, both (V1, V2) and (W1,W2) are ξ(G)-pairs, where V2 is a γ(G)-set and
|V1|+ |V2| > γt(G), while W2 is a γt(G)-set which does not contain any γ(G)-set.
The following bounds were given in [5]. In fact the lower bound was stated for any
connected non-trivial graph G, although it also holds for any graph G with no isolated
vertex.
Theorem 3.4 ([5]). For any graph H and any graph G with no isolated vertex,
γtR(G) ≤ γtR(G ◦H) ≤ 2γt(G).
Furthermore, if γ(H) = 1, then
γtR(G ◦H) ≤ 3γ(G).
In order to improve some of these bounds, we need to introduce some additional termi-
nology. Given a set S ⊆ V (G), we define
ψ(S) = min{|S′| : S′ ⊆ V (G) \ S and S ⊆ N(S′ ∪ S)}.
We also define the following parameter associated to G.
µ(G) = min{ψ(S) : S is a γ(G)-set}.
It is readily seen that 0 ≤ µ(G) ≤ γ(G). Furthermore, µ(G) = 0 if and only if γt(G) =
γ(G), while µ(G) = γ(G) if and only if for every γ(G)-set S and every pair of different
vertices x, y ∈ S we have that N [x] ∩ N [y] = ∅, i.e., if and only if every γ(G)-set is a
2-packing of G.
With the notation above in mind, we state the following theorem.
Theorem 3.5. Let G and H be two graphs with no isolated vertex. If γ(H) = 1, then
max{γtR(G), γt(G) + γ(G)} ≤ γtR(G ◦H) ≤ min{2γ(G) + µ(G), 2γt(G)}.
Proof. Our main tool is Theorem 3.3. For any ξ(G)-pair (A,B) we have that γtR(G◦H) =
ξ(G) = 2|B|+ |A| ≥ |(A ∪B)|+ |B| ≥ γt(G) + γ(G).
Now, let S be a γ(G)-set with µ(G) = ψ(S) and S′ ⊆ V (G) \ S a set of minimum
cardinality among the subsets of V (G)\S satisfying that S ⊆ N(S′∪S). Since S∪S′ is a
total dominating set, γtR(G◦H) = ξ(G) ≤ |S∪S′|+ |S| = 2|S|+ |S′| = 2γ(G)+µ(G).
Finally, by Theorem 3.4, γtR(G) ≤ γtR(G ◦ H) ≤ 2γt(G), which completes the
proof.
238 Ars Math. Contemp. 20 (2021) 233–241
Since µ(G) ≤ γ(G), we can conclude that the bound γtR(G ◦ H) ≤ 2γ(G) + µ(G)
is never worse than the known bound γtR(G ◦ H) ≤ 3γ(G). In order to see that the
upper bounds given by Theorem 3.5 are tight, we take the graph G shown in
Figure 1 and any nontrivial graphH with γ(H) = 1. In this case, γtR(G◦H) = 2γt(G) =
2γ(G) + µ(G) = 8.
We would point out the following result which is a direct consequence of Theorems 2.2
and 3.5.
Theorem 3.6. If G is a graph with γt(G) = γ(G) and H is a nontrivial graph with
γ(H) = 1, then
γtR(G ◦H) = γtR(G) = 2γ(G).
We now proceed to characterize the graphs achieving the lower bounds given by Theo-
rem 3.5.
Theorem 3.7. Let G and H be two graphs with no isolated vertex. If γ(H) = 1, then the
following statements are equivalent.
(i) γtR(G ◦H) = γtR(G).
(ii) There exists a γtR(G)-function f(V0, V1, V2) such that V2 is dominating set of G.
Proof. If there exists a γtR(G)-function f(V0, V1, V2) such that V2 is dominating set of
G, then γtR(G ◦ H) = ξ(G) ≤ |V1 ∪ V2| + |V2| = |V1| + 2|V2| = γtR(G). Since
γtR(G) ≤ γtR(G ◦H), we conclude that γtR(G ◦H) = γtR(G).
Conversely, assume that γtR(G ◦ H) = γtR(G). Let g(V ′0 , V ′1 , V ′2) be a γtR(G ◦ H)-
function satisfying Lemma 3.1. Let A = {x ∈ V (G) : g(V (Hx)) = 1} and B = {x ∈
V (G) : g(V (Hx)) = 2}. By Lemma 3.2, B is a dominating set of G and A ∪ B is a total
dominating set. Hence, we can define a TRDF h(V ′′0 , V
′′
1 , V
′′
2 ) from V
′′
1 = A and V
′′
2 = B.
Since ω(h) = |A|+ 2|B| = |V ′1 |+ 2|V ′2 | = γtR(G ◦H) = γtR(G), we conclude that h is
a γtR(G)-function where V ′′2 is a dominating set, as desired.
The next result gives a characterization for the case γtR(G ◦ H) = γt(G) + γ(G)
whenever γ(H) = 1.
Theorem 3.8. Let G and H be two graphs with no isolated vertex. If γ(H) = 1, then the
following statement are equivalent.
(i) γtR(G ◦H) = γt(G) + γ(G).
(ii) There exists a γt(G)-set that contains some γ(G)-set.
Proof. If there exists a γt(G)-set X which contains a γ(G)-set B, then γtR(G ◦ H) =
ξ(G) ≤ |X \ B| + 2|B| = |X| + |B| = γt(G) + γ(G), and by (i) we conclude that
γtR(G ◦H) = γt(G) + γ(G).
Conversely, assume that γtR(G◦H) = γt(G)+γ(G) and let (A,B) be a ξ(G)-pair. If
the total dominating setA∪B is a γt(G)-set, then we are done, asB is a dominating set and
from γt(G)+ γ(G) = γtR(G ◦H) = ξ(G) = |A|+2|B| = |A∪B|+ |B| = γt(G)+ |B|
we deduce that B is a γ(G)-set. Suppose to the contrary, that |A ∪ B| > γt(G). In such a
case, γt(G) + γ(G) = ξ(G) = |A|+ 2|B| ≥ |A ∪B|+ |B| > γt(G) + γ(G), which is a
contradiction. Therefore, the result follows.
Figure 2 shows a graph G such that γtR(G ◦H) = γt(G) + γ(G) = 7 > 6 = γtR(G)
for every nontrivial graph H with γ(H) = 1.
A. Cabrera Martı́nez and J. A. Rodrı́guez-Velázquez: Closed formulas for the total Roman . . . 239
a
db c e
Figure 2: The γt(G)-set D = {a, b, d, e} contains the γ(G)-set S = {a, b, d}.
4 Small values of γtR(G ◦ H)
In this short section we characterize the graphs G and H for which γtR(G ◦H) ∈ {3, 4}.
Theorem 4.1. For any graph G and H with no isolated vertex, the following statements
are equivalent.
(i) γtR(G ◦H) = 3.
(ii) γ(G) = γ(H) = 1.
Proof. If γtR(G ◦ H) = 3, then by Theorem 2.4 we deduce that γ(H) = 1. Moreover,
by Theorem 3.5 we have that 3 = γtR(G ◦H) ≥ γt(G) + γ(G) ≥ 3. Hence, γ(G) = 1,
as required. Conversely, if γ(G) = γ(H) = 1, then by Theorem 3.8 we deduce that
γtR(G ◦H) = 3.
Theorem 4.2. For any graph G and H with no isolated vertex, γtR(G ◦ H) = 4 if and
only if one of the following conditions are satisfied.
(i) γt(G) = 2 and γ(H) ≥ 2.
(ii) γt(G) = γ(G) = 2 and γ(H) = 1.
Proof. We first notice that if conditions (i) or (ii) holds, then by Theorem 2.4 or by Theo-
rem 3.5, respectively, it follows that γtR(G ◦H) = 4.
Conversely, assume that γtR(G ◦ H) = 4. If γ(H) ≥ 2, then Theorem 2.4 leads to
γt(G) = 2. From now on, we assume that γ(H) = 1. By Theorem 3.8, we have that
4 = γtR(G ◦ H) ≥ γt(G) + γ(G). Hence, 1 ≤ γ(G) ≤ 2. If γ(G) = 1, then by
Theorem 4.1 we obtain that γtR(G ◦H) = 3, which is a contradiction. Hence, γ(G) = 2
and so γt(G) = 2. Therefore, the result follows.
5 Open problems
By Theorem 3.3 we learned that, if we want to know the behaviour of γtR(G ◦ H) when
γ(H) = 1, then it is crucial to obtain the exact value or derive tight bounds on ξ(G). In
this sense, the study of ξ(G) is an interesting challenge.
In particular, Theorem 3.5 states that
max{γtR(G), γt(G) + γ(G)} ≤ ξ(G) ≤ min{2γ(G) + µ(G), 2γt(G)}.
The graphs achieving the equalities ξ(G) = γtR(G) and ξ(G) = γt(G)+ γ(G) were char-
acterized in Theorems 3.7 and 3.8, respectively. Therefore, the problems of characterizing
the graphs achieving the equalities ξ(G) = 2γt(G) and ξ(G) = 2γ(G) + µ(G) = 3γ(G)
remain open.
240 Ars Math. Contemp. 20 (2021) 233–241
ORCID iDs
Abel Cabrera Martı́nez https://orcid.org/0000-0003-2806-4842
Juan Alberto Rodrı́guez-Velázquez https://orcid.org/0000-0002-9082-7647
References
[1] H. Abdollahzadeh Ahangar, M. A. Henning, V. Samodivkin and I. G. Yero, Total Ro-
man domination in graphs, Appl. Anal. Discrete Math. 10 (2016), 501–517, doi:10.2298/
aadm160802017a.
[2] B. H. Arriola and S. R. Canoy, Jr., Doubly connected domination in the corona and lexico-
graphic product of graphs, Appl. Math. Sci. 8 (2014), 1521–1533, doi:10.12988/ams.2014.
4136.
[3] 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.
[4] A. Cabrera Martı́nez and J. A. Rodrı́guez-Velázquez, Total protection of lexicographic product
graphs, Discuss. Math. Graph Theory (2020), in press, doi:10.7151/dmgt.2318.
[5] N. Campanelli and D. Kuziak, Total Roman domination in the lexicographic product of graphs,
Discrete Appl. Math. 263 (2019), 88–95, doi:10.1016/j.dam.2018.06.008.
[6] M. Dettlaff, M. Lemańska, J. A. Rodrı́guez-Velázquez and R. Zuazua, On the super domination
number of lexicographic product graphs, Discrete Appl. Math. 263 (2019), 118–129, doi:10.
1016/j.dam.2018.03.082.
[7] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Discrete Mathematics
and its Applications, CRC Press, Boca Raton, FL, 2nd edition, 2011, doi:10.1201/b10959.
[8] T. W. Haynes, S. T. Hedetniemi and P. J. Slater (eds.), Domination in Graphs, Volume 2: Ad-
vanced Topics, volume 209 of Monographs and Textbooks in Pure and Applied Mathematics,
Marcel Dekker, New York, 1998, doi:10.1201/9781315141428.
[9] 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.
[10] M. A. Henning, A survey of selected recent results on total domination in graphs, Discrete
Math. 309 (2009), 32–63, doi:10.1016/j.disc.2007.12.044.
[11] 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.
[12] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley-Interscience
Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
[13] D. J. Klein and J. A. Rodrı́guez-Velázquez, Protection of lexicographic product graphs, Dis-
cuss. Math. Graph Theory (2019), in press, doi:10.7151/dmgt.2243.
[14] T. Kraner Šumenjak, P. Pavlič and A. Tepeh, On the Roman domination in the lexicographic
product of graphs, Discrete Appl. Math. 160 (2012), 2030–2036, doi:10.1016/j.dam.2012.04.
008.
[15] T. Kraner Šumenjak, D. F. Rall and A. Tepeh, Rainbow domination in the lexicographic product
of graphs, Discrete Appl. Math. 161 (2013), 2133–2141, doi:10.1016/j.dam.2013.03.011.
[16] R. Laskar, J. Pfaff, S. M. Hedetniemi and S. T. Hedetniemi, On the algorithmic complexity
of total domination, SIAM J. Algebraic Discrete Methods 5 (1984), 420–425, doi:10.1137/
0605040.
A. Cabrera Martı́nez and J. A. Rodrı́guez-Velázquez: Closed formulas for the total Roman . . . 241
[17] C.-H. Liu and G. J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26
(2013), 608–619, doi:10.1007/s10878-012-9482-y.
[18] J. Liu, X. Zhang and J. Meng, Domination in lexicographic product digraphs, Ars Combin. 120
(2015), 23–32.
[19] R. J. Nowakowski and D. F. Rall, Associative graph products and their independence, domina-
tion and coloring numbers, Discuss. Math. Graph Theory 16 (1996), 53–79, doi:10.7151/dmgt.
1023.
[20] M. Valveny, H. Pérez-Rosés and J. A. Rodrı́guez-Velázquez, On the weak Roman domination
number of lexicographic product graphs, Discrete Appl. Math. 263 (2019), 257–270, doi:10.
1016/j.dam.2018.03.039.
[21] X. Zhang, J. Liu and J. Meng, Domination in lexicographic product graphs, Ars Combin. 101
(2011), 251–256.