DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

M.A. Henning, S. Pal, D. Pradhan

Title:

The semitotal domination problem in block graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-04-19, Revised: 2019-09-18, Accepted: 2019-09-24, https://doi.org/10.7151/dmgt.2254

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.

Keywords:

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

PDF
Close