THE GENEROUS ROMAN DOMINATION NUMBER

Let G = (V,E) be a simple graph and f : V → {0, 1, 2, 3} be a function. A vertex u with f (u) = 0 is called an undefended vertex with respect to f if it is not adjacent to a vertex v with f(v) ≥ 2. We call the function f a generous Roman dominating function (GRDF) if for every vertex with f (u) = 0 there exists at least a vertex v with f(v) ≥ 2 adjacent to u such that the function f′ : V → {0, 1, 2, 3}, defined by f′(u) = α, f′(v) = f(v) − α where α = 1 or 2, and f′(w) = f(w) if w ∈ V − {u, v} has no undefended vertex. The weight of a generous Roman dominating function f is the value f(V ) = P u∈V f(u). The minimum weight of a generous Roman dominating function on a graph G is called the generous Roman domination number of G, denoted by γgR (G). In this paper, we initiate the study of generous Roman domination and show its relationships. Also, we give the exact values for paths and cycles. Moreover, we present an upper bound on the generous Roman domination number, and we characterize cubic graphs G of order n with γgR (G) = n−1, and a Nordhaus-Gaddum type inequality for the parameter is also given. Finally, we study the complexity of this parameter.