Vertex and edge critical Roman domination in graphs - Jafari Rad, Nader; Hansberg, Adriana; Volkmann, Lutz (Utilitas Mathematica, 2013)
A Roman dominating function on a graph G is a function f : V(G) → 0, 1, 2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value f(V(G)) = ΣuεV(G) f(u). The Roman domination number γR(G) is the minimum weight of a Roman dominating function on G. In this paper, we study the graphs for which removing any vertex (or adding any new edge) decreases the Roman domination number. We call these graphs γR-vertex (or -edge) critical. We present some families of γR-vertex and -edge critical graphs and we characterize γR-vertex critical block graphs, as well as γR-edge critical trees.