Complexity and approximation ratio of semitotal domination in graphs

Document Type: Original paper

Authors

Guangzhou University

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

Main Subjects