An upper bound on triple Roman domination

Communications in Combinatorics and Optimization

article

M. Hajjari¹  Hossein Abdollahzadeh Ahangar²  Rana Khoeilar¹  Zehui Shao³  S.M. Sheikholeslami¹ 

[1]Azarbaijan Shahid Madani University

[2]Babol Noshirvani University of Technology

[3]Guangzhou University

关键词: Triple Roman dominating function;    Triple Roman domination number;    Trees;   

DOI  :  10.22049/cco.2022.27816.1359

学科分类：社会科学、人文和艺术（综合）

来源: Azarbaijan Shahide Madani Universit

【 摘 要 】

For a graph $G=(V,E)$, a triple Roman dominating function (3RD-function) is a function $f:V\to \{0,1,2,3,4\}$ having the property that (i) if $f(v)=0$ then $v$ must have either one neighbor $u$ with $f(u)=4$, or two neighbors $u,w$ with $f(u)+f(w)\ge 5$ or three neighbors $u,w,z$ with $f(u)=f(w)=f(z)=2$, (ii) if $f(v)=1$ then $v$ must have one neighbor $u$ with $f(u)\ge 3$ or two neighbors $u,w$ with $f(u)=f(w)=2$, and (iii) if $f(v)=2$ then $v$ must have one neighbor $u$ with $f(u)\ge 2$. The weight of a 3RDF $f$ is the sum $f(V)=\sum_{v\in V} f(v)$, and the minimum weight of a 3RD-function on $G$ is the triple Roman domination number of $G$, denoted by $\gamma_{[3R]}(G)$. In this paper, we prove that for any connected graph $G$ of order $n$ with minimum degree at least two,  $\gamma_{[3R]}(G)\leq \frac{3n}{2}$.

【 授权许可】

CC BY-SA