@article {
author = {Shao, Zehui and Wu, Pu},
title = {Complexity and approximation ratio of semitotal domination in graphs},
journal = {Communications in Combinatorics and Optimization},
volume = {3},
number = {2},
pages = {143-150},
year = {2018},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2018.25987.1065},
abstract = {A set $S subseteq V(G)$ is a semitotal dominating set of a graph $G$ if it is a dominating set of $G$ andevery vertex in $S$ is within distance 2 of another vertex of $S$. Thesemitotal domination number $gamma_{t2}(G)$ is the minimumcardinality of a semitotal dominating set of $G$.We show that the semitotal domination problem isAPX-complete for bounded-degree graphs, and the semitotal domination problem in any graph of maximum degree $Delta$ can be approximated with an approximationratio of $2+ln(Delta-1)$.},
keywords = {semitotal domination,APX-complete,NP-completeness},
url = {http://comb-opt.azaruniv.ac.ir/article_13748.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13748_70d5d03f125812cbc3dc8d0aec38312f.pdf}
}