10.46298/dmtcs.6782
Henning, Michael A.
Michael A.
Henning
Pandey, Arti
Arti
Pandey
Tripathi, Vikash
Vikash
Tripathi
Semipaired Domination in Some Subclasses of Chordal Graphs
episciences.org
2021
Computer Science - Discrete Mathematics
Computer Science - Computational Complexity
contact@episciences.org
episciences.org
2020-09-15T14:29:32+02:00
2021-08-23T23:08:41+02:00
2021-07-06
eng
Journal article
https://dmtcs.episciences.org/6782
arXiv:2008.13491
1365-8050
PDF
1
Discrete Mathematics & Theoretical Computer Science ; vol. 23 no. 1 ; Discrete Algorithms ; 1365-8050
A dominating set $D$ of a graph $G$ without isolated vertices is called
semipaired dominating set if $D$ can be partitioned into $2$-element subsets
such that the vertices in each set are at distance at most $2$. The semipaired
domination number, denoted by $\gamma_{pr2}(G)$ is the minimum cardinality of a
semipaired dominating set of $G$. Given a graph $G$ with no isolated vertices,
the \textsc{Minimum Semipaired Domination} problem is to find a semipaired
dominating set of $G$ of cardinality $\gamma_{pr2}(G)$. The decision version of
the \textsc{Minimum Semipaired Domination} problem is already known to be
NP-complete for chordal graphs, an important graph class. In this paper, we
show that the decision version of the \textsc{Minimum Semipaired Domination}
problem remains NP-complete for split graphs, a subclass of chordal graphs. On
the positive side, we propose a linear-time algorithm to compute a minimum
cardinality semipaired dominating set of block graphs. In addition, we prove
that the \textsc{Minimum Semipaired Domination} problem is APX-complete for
graphs with maximum degree $3$.