Computing Roman domatic number of graphs

• We show that it is NPNP-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)Θ(log⁡n) for approximating the Roman domatic number of a graph.
• Finally, we also determine the exact values of the Roman domatic number in some particular classes of graphs.

A Roman dominating function   on a graph G=(V,E)G=(V,E) is a mapping: V→{0,1,2}V→{0,1,2} satisfying that every vertex v∈Vv∈V with f(v)=0f(v)=0 is adjacent to some vertex u∈Vu∈V with f(u)=2f(u)=2. A Roman dominating family (of functions) on G   is a set {f1,f2,…,fd}{f1,f2,…,fd} of Roman dominating functions on G   with the property that ∑i=1dfi(v)≤2 for all v∈Vv∈V. The Roman domatic number of G, introduced by Sheikholeslami and Volkmann in 2010 [1], is the maximum number of functions in a Roman dominating family on G  . In this paper, we study the Roman domatic number from both algorithmic complexity and graph theory points of view. We show that it is NPNP-complete to decide whether the Roman domatic number is at least 3, even if the graph is bipartite. To the best of our knowledge, this is the first computational hardness result concerning this concept. We also present an asymptotically optimal approximation threshold of Θ(log⁡n)Θ(log⁡n) for computing the Roman domatic number of a graph. Moreover, we determine the Roman domatic number of some particular classes of graphs, such as fans, wheels and complete bipartite graphs.