Michael A. Henning ; Arti Pandey ; Vikash Tripathi - Semipaired Domination in Some Subclasses of Chordal Graphs

dmtcs:6782 - Discrete Mathematics & Theoretical Computer Science, July 6, 2021, vol. 23 no. 1 - https://doi.org/10.46298/dmtcs.6782
Semipaired Domination in Some Subclasses of Chordal GraphsArticle

Authors: Michael A. Henning ; Arti Pandey ; Vikash Tripathi ORCID

    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$.


    Volume: vol. 23 no. 1
    Section: Discrete Algorithms
    Published on: July 6, 2021
    Accepted on: June 14, 2021
    Submitted on: September 15, 2020
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 644 times.
    This article's PDF has been downloaded 342 times.