TY - JOUR
ID - 14264
TI - Algorithmic aspects of total Roman $\{2\}$-domination in graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - P, Chakradhar
AU - P, Venkata Subba Reddy
AD - National Institute of Technology, Warangal
Y1 - 2022
PY - 2022
VL - 7
IS - 2
SP - 183
EP - 192
KW - Roman ${2}$-dominating function
KW - Total Roman ${2}$-domination
KW - APX-complete
DO - 10.22049/cco.2021.27063.1189
N2 - For a simple, undirected, connected graph $G$, a function $h : V \rightarrow \lbrace 0, 1, 2 \rbrace$ is called a total Roman $\{2\}$-dominating function (TR2DF) if for every vertex $v$ in $V$ with weight $0$, either there exists a vertex $u$ in $N_G(v)$ with weight $2$, or at least two vertices $x, y$ in $N_G(v)$ each with weight $1$, and the subgraph induced by the vertices with weight more than zero has no isolated vertices. The weight of TR2DF $h$ is $\sum_{p \in V} h(p)$. The problem of determining TR2DF of minimum weight is called minimum total Roman \{2\}-domination problem (MTR2DP). We show that MTR2DP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a $2 (\ln(\Delta - 0.5) + 1.5)$-approximation algorithm for the MTR2DP and show that the same cannot have $(1 - \delta) \ln |V|$ ratio approximation algorithm for any $\delta > 0$ unless $P = NP$. Next, we show that MTR2DP is APX-hard for graphs with $ \Delta=4$. Finally, we show that the domination and TR2DF problems are not equivalent in computational complexity aspects.
UR - https://comb-opt.azaruniv.ac.ir/article_14264.html
L1 - https://comb-opt.azaruniv.ac.ir/article_14264_93fdd90572f39e706ad1feba0e1d4260.pdf
ER -