Co-Roman domination in graphs

Abstract

Let G = (V,E) be a graph and let f : V → {0, 1, 2} be a function. A vertex u is said to be protected with respect to f if f(u) > 0 or f(u) = 0 and u is adjacent to a vertex with positive weight. The function f is a co-Roman dominating function (CRDF) if: (i) every vertex in V is protected, and (ii) each v ∈ V with f(v) > 0 has a neighbor u ∈ V with f(u) = 0 such that the function f _vu : V → {0, 1, 2}, defined by f _vu (u) = 1, f _vu (v) = f(v) −1 and f _vu (x) = f(x) for x ∈ V ∖ {u, v} has no unprotected vertex. The weight of f is $w(f)={\sum }_{v\in V}f(v)$. The co-Roman domination number of a graph G, denoted by γ _{c r} (G), is the minimum weight of a co-Roman dominating function on G. In this paper we initiate a study of this parameter, present several basic results, as well as some applications and directions for further research. We also show that the decision problem for the co-Roman domination number is NP-complete, even when restricted to bipartite, chordal and planar graphs.