A note on Roman domination in graphs

Let G = (V, E) be a simple graph. A subset S subset of V is a dominating set of G, if for any vertex u is an element of V - S, there exists a vertex v is an element of S such that uv is an element of E. The domination number of G, gamma(G), equals the minimum cardinality, of a dominating set. A Roman dominating function on graph G = (V, E) is a function f : V -> {0, 1, 2} satisfying the condition that every vertex v for which f (v) = 0 is adjacent to at least one vertex u for which f (u) = 2. The weight of a Roman dominating function is the value f (V) = Sigma V-v is an element of f (v). The Roman domination number of a graph G, denoted by gamma(R) (G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k (2 <= k <= gamma(G)), we give a characterization of graphs for which gamma(R)(G) = gamma(G) + k, which settles an open problem in [ET Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22]. (c) 2006 Elsevier B.V. All rights reserved.