## Abstract

A set D of vertices in a graph G is a dominating set of G if every vertex outside D is adjacent in G to some vertex in D. A set D of vertices in G is a semitotal dominating set of G if D is a dominating set of G and every vertex in D is within distance 2 from another vertex of D. Given a graph G and a positive integer k, the semitotal domination problem is to decide whether G has a semitotal dominating set of cardinality at most k. The semitotal domination problem is known to be NP-complete for chordal graphs and bipartite graphs as shown in [M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46-57]. In this paper, we present a linear time algorithm to compute a minimum semitotal dominating set in block graphs. On the other hand, we show that the semitotal domination problem remains NP-complete for undirected path graphs.

Original language | English |
---|---|

Journal | Discussiones Mathematicae - Graph Theory |

DOIs | |

Publication status | Accepted/In press - 2019 |

## Keywords

- NP-complete
- block graphs
- domination
- semitotal domination
- undirected path graphs

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics