ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2019: 0.600
Rejection Rate (2018-2019): c. 84%
Article in press
M.A. Henning, S. Pal, D. Pradhan
The semitotal domination problem in block graphs
Discussiones Mathematicae Graph Theory
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.
domination, semitotal domination, block graphs, undirected path