Co-Roman domination in graphs

[摘要] Let $G = (V,E)$ be a graph and let $f:V→ {0, 1, 2}$ be a function. A vertex 𝑢 is said to be protected with respect to 𝑓 if $f(u)> 0$ or $f(u)=0$ and 𝑢 is adjacent to a vertex with positive weight. The function 𝑓 is a co-Roman dominating function (CRDF) if: (i) every vertex in 𝑉 is protected, and (ii) each $v in V$ with $f(v) > 0$ has a neighbor $uin 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 $xin Vackslash {u,v}$ has no unprotected vertex. The weight of 𝑓 is $w(f)=𝛴_{vin V} f(v)$. The co-Roman domination number of a graph 𝐺, denoted by $𝛾_{cr}(G)$, is the minimum weight of a co-Roman dominating function on 𝐺. 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.

[学科分类] 数学（综合）

[关键词] Domination;Roman domination;weak Roman domination;co-Roman domination.