LAUSR

For a simple, undirected graph $$G = (V, E)$$ G = ( V , E ) , a Roman dominating function (RDF) $$f{:}V \rightarrow \lbrace 0, 1, 2 \rbrace $$ f : V → { 0 , 1 , 2 } has the property that, every vertex u with $$f(u) = 0$$ f ( u ) = 0 is adjacent to at least one vertex v for which $$f(v) = 2$$ f ( v ) = 2 . The weight of a RDF is the sum $$f(V) = \sum _{v \in V}f(v)$$ f ( V ) = ∑ v ∈ V f ( v ) . The minimum weight of a RDF is called the Roman domination number and is denoted by $$\gamma _{R}(G)$$ γ R ( G ) . Given a graph G and a positive integer k , the Roman domination problem (RDP) is to check whether G has a RDF of weight at most k . The RDP is known to be NP-complete for bipartite graphs. We strengthen this result by showing that this problem remains NP-complete for two subclasses of bipartite graphs namely, star convex bipartite graphs and comb convex bipartite graphs. We show that $$\gamma _{R}(G)$$ γ R ( G ) is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs. The minimum Roman domination problem (MRDP) is to find a RDF of minimum weight in the input graph. We show that the MRDP for star convex bipartite graphs and comb convex bipartite graphs cannot be approximated within $$(1 - \epsilon ) \ln |V|$$ ( 1 - ϵ ) ln | V | for any $$\epsilon > 0$$ ϵ > 0 unless $$NP \subseteq DTIME(|V|^{O(\log \log |V|)})$$ N P ⊆ D T I M E ( | V | O ( log log | V | ) ) and also propose a $$2(1+\ln (\varDelta +1))$$ 2 ( 1 + ln ( Δ + 1 ) ) -approximation algorithm for the MRDP, where $$\varDelta $$ Δ is the maximum degree of G . Finally, we show that the MRDP is APX-complete for graphs with maximum degree 5.