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

Identifier:  imarina:9232644

Handle: https://hdl.handle.net/20.500.11797/imarina9232644

Authors:  Martinez, Abel Cabrera; Rodriguez-Velazquez, Juan Alberto

Abstract:
Let G be a graph with no isolated vertex and f: V (G) -> {0, 1, 2} a function. Let V-i = {x is an element of V(G): f(x) = i} for every i is an element of {0, 1, 2}. We say that f is a total Roman dominating function on G if every vertex in V-0 is adjacent to at least one vertex in V-2 and the subgraph induced by V-1 boolean OR V-2 has no isolated vertex. The weight of f is omega(f) = Sigma(v is an element of 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 gamma(tR)circle(G). It is known that the general problem of computing gamma(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 circle H is given bygamma(tR)(G o H) = {2 gamma t(G) if gamma(H) >= 2,xi(G) if gamma(H) =1,where gamma(H) is the domination number of H, gamma(t)(G) is the total domination number of G and xi(G) is a domination parameter defined on G.