The Characterizations and Complexity of Roman {2}-Domination and 2-Domination in Graphs

A Roman {2}-dominating function on a graph G is a function \(f: V(G)\rightarrow \{0, 1, 2\}\) satisfying \(\sum _{u\in N_G(v)}f(u)\ge 2\) for each vertex v with \(f(v)=0\) , where \(N_G(v)\) is the neighborhood of v in G. The weight of a Roman {2}-dominating function f is the sum \(\sum _{u\in V(G)}f(u)\) , and the minimum weight of a Roman {2}-dominating function f on a graph G is called the Roman {2}-domination number of G, denoted by \(\gamma _{\{R2\}}(G)\) . A 2-dominating set of a graph G is a subset S of V(G) such that each vertex in \(V(G)\backslash S\) is adjacent to at least two vertices in S. The 2-domination number \(\gamma _2(G)\) is the minimum cardinality of a 2-dominating set of G. Chellali et al. proved that for every graph G, \(\gamma _{\{R2\}}(G)\le \gamma _{2}(G)\) . In this paper, we first characterize the trees T for which \(\gamma _{\{R2\}}(T)=\gamma _{2}(T)\) . Then we give a lower bound of \(\gamma _{\{R2\}}(T)\) for a tree T depending on \(\gamma _{2}(T)\) and the number of leaves l of tree T: \(\gamma _{2}(T)-l+2\le \gamma _{\{R2\}}(T)\) , and characterize the trees T for which \(\gamma _{2}(T)-l+2=\gamma _{\{R2\}}(T)\) . Finally we show that the decision problem that whether for a given graph G, \(\gamma _{\{R2\}}(G)=\gamma _{2}(G)\) is NP-hard even when restricted to bipartite graphs.