|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Semipaired Domination in Some Subclasses of Chordal Graphs | | Michael A. Henning
; Arti Pandey
; Vikash Tripathi
; | | Date: |
31 Aug 2020 | | Abstract: | 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 extsc{Minimum Semipaired Domination} problem is to find a semipaired
dominating set of $G$ of cardinality $gamma_{pr2}(G)$. The decision version of
the extsc{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 extsc{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 extsc{Minimum Semipaired Domination} problem is APX-complete for
graphs with maximum degree $3$. | | Source: | arXiv, 2008.13491 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER