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

Abel Cabrera Martínez ; Juan Alberto Rodríguez-Velázquez

Ars Mathematica Contemporanea, Tome 20 (2021) no. 2, pp. 233-241.

Résumé

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.

Détail

DOI : 10.26493/1855-3974.2284.aeb

Keywords: Total Roman domination, total domination, lexicographic product graph