Algorithmic aspects of total Roman ${2}$-domination in graphs
Author(s):
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:
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.
Language:
English
Published:
Communications in Combinatorics and Optimization, Volume:7 Issue: 2, Summer-Autumn 2022
Pages:
183 to 192
https://www.magiran.com/p2418093