A linear-time algorithm for semitotal domination in strongly chordal graphs
share
In a graph G=(V,E) with no isolated vertex, a dominating set D ⊆ V, is called a semitotal dominating set if for every vertex u ∈ D there is another vertex v ∈ D, such that distance between u and v is at most two in G. Given a graph G=(V,E) without isolated vertices, the Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of G. The semitotal domination number, denoted by γ_t2(G), is the minimum cardinality of a semitotal dominating set of G. The decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. Galby et al. in [6] proved that the problem can be solved in polynomial time for bounded MIM-width graphs which includes many well known graph classes, but left the complexity of the problem in strongly chordal graphs unresolved. Henning and Pandey in [20] also asked to resolve the complexity status of the problem in strongly chordal graphs. In this paper, we resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem.
READ FULL TEXT