Geodesic
Semipaired Domination in Some Subclasses of Chordal Graphs
Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 1.

Voir la notice de l'article provenant de la source Episciences

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$.
DOI : 10.46298/dmtcs.6782
Classification : 05B05, 05C69, 05C85 
@article{DMTCS_2021_23_1_a16,
     author = {Henning, Michael A. and Pandey, Arti and Tripathi, Vikash},
     title = {Semipaired {Domination} in {Some} {Subclasses} of {Chordal} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2021-2022},
     doi = {10.46298/dmtcs.6782},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6782/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Pandey, Arti
AU  - Tripathi, Vikash
TI  - Semipaired Domination in Some Subclasses of Chordal Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2021-2022
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6782/
DO  - 10.46298/dmtcs.6782
LA  - en
ID  - DMTCS_2021_23_1_a16
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Pandey, Arti
%A Tripathi, Vikash
%T Semipaired Domination in Some Subclasses of Chordal Graphs
%J Discrete mathematics & theoretical computer science
%D 2021-2022
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6782/
%R 10.46298/dmtcs.6782
%G en
%F DMTCS_2021_23_1_a16
Henning, Michael A.; Pandey, Arti; Tripathi, Vikash. Semipaired Domination in Some Subclasses of Chordal Graphs. Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 1. doi : 10.46298/dmtcs.6782. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6782/

Cité par Sources :