Complexity and approximation ratio of semitotal domination in graphs

Author(s):

Zehui Shao * , Pu Wu

Message:
Article Type:
Research/Original Article (بدون رتبه معتبر)
Abstract:
A set $S subseteq V(G)$ is a semitotal dominating set of a graph $G$ if it is a dominating set of $G$ and every vertex in $S$ is within distance 2 of another vertex of $S$. The semitotal domination number $gamma_{t2}(G)$ is the minimum cardinality of a semitotal dominating set of $G$. We show that the semitotal domination problem is APX-complete for bounded-degree graphs, and the semitotal domination problem in any graph of maximum degree $Delta$ can be approximated with an approximation ratio of $2+ln(Delta-1)$.
Keywords:

semitotal domination , APX-complete , NP-completeness

Language:
English
Published:
Communications in Combinatorics and Optimization, Volume:3 Issue: 2, Summer and Autumn 2018
Pages:
143 to 150
https://www.magiran.com/p1908614