TY - JOUR
ID - 13748
TI - Complexity and approximation ratio of semitotal domination in graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Shao, Zehui
AU - Wu, Pu
AD - Guangzhou University
Y1 - 2018
PY - 2018
VL - 3
IS - 2
SP - 143
EP - 150
KW - semitotal domination
KW - APX-complete
KW - NP-completeness
DO - 10.22049/cco.2018.25987.1065
N2 - 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)$.
UR - http://comb-opt.azaruniv.ac.ir/article_13748.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13748_70d5d03f125812cbc3dc8d0aec38312f.pdf
ER -