Dominating the direct product of two graphs through total Roman strategies

Abstract

Given a graph $G$ without isolated vertices, a total Roman dominating function for $G$ is a function $f:V(G)\to \{0,1,2\}$ such that every vertex with label 0 is adjacent to a vertex with label 2, and the set of vertices with positive labels induces a graph of minimum degree at least one. The total Roman domination number ${\gamma }_{tR}(G)$ of $G$ is the smallest possible value of ${\sum }_{v\in V(G)}f(v)$ among all total Roman dominating functions $f$. The total Roman domination number of the direct product $G\times H$ of the graphs $G$ and $H$ is studied in this work. Specifically, several relationships, in the shape of upper and lower bounds, between ${\gamma }_{tR}(G\times H)$ and some classical domination parameters for the factors are given. Characterizations of the direct product graphs $G\times H$ achieving small values ($\le 7$) for ${\gamma }_{tR}(G\times H)$ are presented, and exact values for ${\gamma }_{tR}(G\times H)$ are deduced, while considering various specific direct product classes.

16 pages