Maximal Roman domination numbers in graphs

Abstract

A Roman dominating function on a graph G is a labeling f : V(G) {0,1,2} such that every vertex with label 0 has a neighbor with label 2. A maximal Roman dominating function on a graph G is a Roman dominating function / such that Vo = {ω ϵ V(G) f(w)} is not a dominating set of G. The weight of a maximal Roman dominating function is the value w(f) = f{V{G)) = ϵxϵV(G) F(x) The maximal Roman domination number γmr(G)of graph G equals the minimum weight of an maximal Roman dominating function on G. In this paper we initiate the study of maximal Roman domination number in graphs and we present some sharp bounds for γmr(G). In addition, we determine the maximal Roman domination number of some graphs. © 2015 Utilitas Mathematics.