%0 Journal Article
%T Complexity and approximation ratio of semitotal domination in graphs
%J Communications in Combinatorics and Optimization
%I Azarbaijan Shahid Madani University
%Z 2538-2128
%A Shao, Zehui
%A Wu, Pu
%D 2018
%\ 12/01/2018
%V 3
%N 2
%P 143-150
%! Complexity and approximation ratio of semitotal domination in graphs
%K semitotal domination
%K APX-complete
%K NP-completeness
%R 10.22049/cco.2018.25987.1065
%X 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)$.
%U http://comb-opt.azaruniv.ac.ir/article_13748_70d5d03f125812cbc3dc8d0aec38312f.pdf