A linear-time algorithm for semitotal domination in strongly chordal graphs (Q6110593)

A set \(D\) of vertices in an isolate-free graph \(G\) is a semitotal dominating set of \(G\) if \(D\) is a dominating set of \(G\) and every vertex in \(D\) is within distance two from another vertex of \(D\). The semitotal domination number of \(G\) is the minimum cardinality of a semitotal dominating set of \(G\) and is denoted by \(\gamma_{t2}(G)\). The Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of \(G\). It is known that the decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. The authors in this paper, resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem.