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

english

2021

volume 20, issue 2

lexicographic product graph   total domination   total Roman domination

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

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$?.

22.11.2022