The generous Roman domination number

Let G=(V,E)\ be a simple graph and f:V\rightarrow\{۰,۱,۲,۳\} be a function. A vertex u with f\left( u\right) =۰ is called an undefended vertex with respect to f if it is not adjacent to a vertex v with f(v)\geq۲. We call the function f a generous Roman dominating function (GRDF) if for every vertex with f\left( u\right) =۰ there exists at least a vertex v with f(v)\geq۲ adjacent to u such that the function f^{\prime}:V\rightarrow \{۰,۱,۲,۳\}, defined by f^{\prime}(u)=\alpha, f^{\prime}(v)=f(v)-\alpha where \alpha=۱ or ۲, and f^{\prime}(w)=f(w) if w\in V-\{u,v\} has no undefended vertex. The weight of a generous Roman dominating function f is the value f(V)=\sum_{u\in 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 \gamma_{gR}\left( G\right) . 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 \gamma_{gR}\left( G\right) =n-۱, and a Nordhaus-Gaddum type inequality for the parameter is also given. Finally, we study the complexity of this parameter.

Keywords:

Roman domination , Weak Roman domination , Double Roman domination