Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination

Let $$G=(V,E)$$ G = ( V , E ) be a graph. A function $$f : V \rightarrow \{0, 1, 2\}$$ f : V → { 0 , 1 , 2 } is an outer independent Roman dominating function (OIRDF) on a graph G if for every vertex $$v \in V$$ v ∈ V with $$f (v) = 0$$ f ( v ) = 0 there is a vertex u adjacent to v with $$f (u) = 2$$ f ( u ) = 2 and $$\{x\in V:f(x)=0\}$$ { x ∈ V : f ( x ) = 0 } is an independent set. The weight of f is the value $$ f(V)=\sum _{v\in V}f(v)$$ f ( V ) = ∑ v ∈ V f ( v ) . An outer independent total Roman dominating function (OITRDF) f on G is an OIRDF on G such that for every $$v\in V$$ v ∈ V with $$f(v)>0$$ f ( v ) > 0 there is a vertex u adjacent to v with $$f (u)>0$$ f ( u ) > 0 . The minimum weight of an OIRDF on G is called the outer independent Roman domination number of G, denoted by $$\gamma _{oiR}(G)$$ γ oiR ( G ) . Similarly, the outer independent total Roman domination number of G is defined, denoted by $$\gamma _{oitR}(G)$$ γ oitR ( G ) . In this paper, we first show that computing $$\gamma _{oiR}(G)$$ γ oiR ( G ) (respectively, $$\gamma _{oitR}(G)$$ γ oitR ( G ) ) is a NP-hard problem, even when G is a chordal graph. Then, for a given proper interval graph $$G=(V,E)$$ G = ( V , E ) we propose an algorithm to compute $$\gamma _{oiR}(G)$$ γ oiR ( G ) (respectively, $$\gamma _{oitR}(G)$$ γ oitR ( G ) ) in $${\mathcal {O}}(|V| )$$ O ( | V | ) time.