Vertex and edge critical Roman domination in graphs

Abstract

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.