The differential and the roman domination number of a graph

Abstract

Let G = (V,E) be a graph of order n and let B(S) be the set of vertices in V\S that have a neighbor in the vertex set S. The differential of a vertex set S is defined as ?(S) = |B(S)| - |S| and the maximum value of ?(S) for any subset S of V is the differential of G. A Roman dominating function of G is a function f : V ? {0,1,2} such that every vertex u with f(u) = 0 is adjacent to a vertex v with f(v) = 2. The weight of a Roman dominating function is the value f(V) = ?u?V f(u). The minimum weight of a Roman dominating function of a graph G is the Roman domination number of G, written ?R(G). We prove that ?R(G) = n - ?(G) and present several combinatorial, algorithmic and complexity-theoretic consequences thereof.