Closed formulas for the total Roman domination number of lexicographic product graphs

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 on G 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, and γtR(G ∘ H) = ξ(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.