Covering total double Roman domination in graphs

Communications in Combinatorics and Optimization

article

Atieh Teymourzadeh¹  Doost Ali Mojdeh² 

[1] Department of Mathematics, University of Mazandaran;Departtment of Mathematics, University of Mazandaran

关键词: Covering;    Roman domination;    total double Roman domination;   

DOI  :  10.22049/cco.2021.27443.1265

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

来源: Azarbaijan Shahide Madani Universit

【 摘 要 】

For a graph $G$ with no isolated vertex, a covering total double Roman dominating function ($CTDRD$ function) $f$ of $G$ is a total double Roman dominating function ($TDRD$ function) of $G$ for which the set $\{v\in V(G)| f(v)\ne 0\}$ is a vertex cover set. The covering total double Roman domination number $\gamma_{ctdR}(G)$ equals the minimum weight of an $CTDRD$ function on $G$. An $CTDRD$ function on $G$ with weight $\gamma_{ctdR} (G)$ is called a $\gamma_{ctdR} (G)$-function. In this paper, the graphs $G$ with small $\gamma_{ctdR} (G)$ are characterised. We show that the decision problem associated with $CTDRD$ is $NP$-complete even when restricted to planer graphs with maximum degree at most four. We then show that for every graph $G$ without isolated vertices, $\gamma_{oitR}(G)<\gamma_{ctdR}(G)< 2\gamma_{oitR}(G)$ and for every tree $T$, $2\beta(T)+1\leq \gamma_{ctdR}(T)\leq4\beta(T)$, where $\gamma_{oitR}(G)$ and $\beta(T)$ are the outer independent total Roman domination number of $G$, and the minimum vertex cover number of $T$ respectively. Moreover we investigate the $\gamma_{ctdR}$ of corona of two graphs.

【 授权许可】

CC BY-SA