Co-Roman domination in graphs

Proceedings Mathematical Sciences

Martín Manrique¹  S Arumugam³  Karam Ebadi² 

[1] Department of Computer Science, Ball State University, Muncie, IN, USA$$;Department of Computer Science, Liverpool Hope University, Liverpool, UK$$;National Centre for Advanced Research in Discrete Mathematics (𝑛-CARDMATH), Kalasalingam University, Anand Nagar, Krishnankoil , India$$

关键词: Domination;    Roman domination;    weak Roman domination;    co-Roman domination.;   

DOI  :  

学科分类：数学（综合）

来源: Indian Academy of Sciences

【 摘 要 】

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.

【 授权许可】

Unknown