Algorithmic Aspects of Semitotal Domination in Graphs
Arti Pandey
Indian Institute of Technology Ropar

For a graph $G = (V, E)$, a set $D\subseteq V$ is called a semitotal dominating set of $G$ if $D$ is a dominating set of $G$, and every vertex in $D$ is within distance 2 of another vertex of $D$. The MINIMUM SEMITOTAL DOMINATION problem is to find a semitotal dominating set of minimum cardinality. Given a graph $G$ and a positive integer $k$, the SEMITOTAL DOMINATION DECISION problem is to decide whether $G$ has a semitotal dominating set of cardinality at most $k$. The SEMITOTAL DOMINATION DECISION problem is known to be NP-complete for general graphs. We will show that the SEMITOTAL DOMINATION DECISION problem remains NP-complete for planar graphs, split graphs and chordal bipartite graphs. We also give a polynomial time algorithm to solve the MINIMUM SEMITOTAL DOMINATION problem in interval graphs.