On maximal Roman domination in graphs
Hossein Abdollahzadeh Ahangar, Mustapha Chellali, Dorota Kuziak, Vladimir Samodivkin · International Journal of Computer Mathematics · 2015
A Roman dominating function (RDF) for a graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex u of G for which f(u)=0 is adjacent to at least one vertex v of G for which f(v)=2. The weight of a RDF f is the sum f(V)=∑v∈Vf(v), and the minimum weight of a RDF for G is the Roman domination number, γR(G), of G. A maximal RDF for a graph G is a RDF f such that V0={w∈V| f(w)=0} is not a dominating set of G. The maximal Roman domination number, γmR(G), of a graph G equals the minimum weight of a maximal RDF for G. We first show that determining the number γmR(G) for an arbitrary graph G is NP-complete even when restricted to bipartite or planar graphs. Then, we characterize connected graphs G such that γmR(G)=γR(G). We also provide a characterization of all trees T of order n such that γmR(T)=n−2.