Computing Roman domatic number of graphs

We show that it is NP -complete to decide whether the Roman domatic number of a given graph is at least three.We then prove an asymptotically optimal threshold of ( log n ) for approximating the Ro...