Closed formulas for the total Roman domination number of lexicographic product graphs - Cabrera Martinez, Abel (Ars mathematica contemporanea, 2021)
Let ?$G$? be a graph with no isolated vertex and ?$f\colon V(G) \to \{0, 1, 2\}$? a function. Let ?$V_i = \{x \in V(G) \colon f(x) = i\}$? for every ?$i \in \{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 \cup V_2$? has no isolated vertex. The weight of ?$f$? is ?$\omega (f)=\sum_{v \in 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}(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 \circ H$? is given by ?$$\gamma_{tR}(G)(G \circ H) = \begin{cases} 2 \gamma_{tR}(G) & \text{if} \; \gamma(H) \ge 2, \\ \xi(G) & \text{if} \; \gamma(H)=1,\end{cases}$$? 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$?.
Keywords: leksikografski produkt grafov; lexicographic product graph; total domination; total Roman domination; totalna dominacija; totalna rimljanska dominacija