Complexity and Algorithmic Results of Restrained Roman Domination

For a simple graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex>, a restrained Roman dominating function (RRDF) is a function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f :V(G)\rightarrow\{0,1,2\}$</tex> possessing the following properties that if a vertex <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$v$</tex> of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex> under RRDF is assigned 0, it has a neighbor <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$u\in N(v)$</tex> assigned 0 and a neighbor <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$w\in N(v)\backslash \{u\}$</tex> is assigned 2. The restrained Roman domination number <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\gamma_{rR}(G)$</tex> is the minimum weight of RRDF of’ <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex>. Given a positive integer <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>, the restrained Roman domination problem (RRDP) is to verify weather <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex> has an RRDF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma_{v\in V(G)}f(v)\leq k$</tex> and the minimum restrained Roman domination problem (MIN-RRDP) is to find a function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex> with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma_{v\in V(G)}f(v)=\gamma_{rR}(G)$</tex>. In this paper, we prove that RRDP is NP-complete even for star convex bipartite graph and comb convex bipartite graph. In addition, we design a linear time algorithm to solve MIN-RRDP for any trees <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex>, which utilize the well-known dynamic programming approach.