Some complexity results on semipaired domination in graphs
Let [Formula: see text] be a graph without any isolated vertices. A semipaired dominating set [Formula: see text] of G, is a dominating set of G, if D can be partitioned into cardinality 2 subsets such that the vertices in each of these subsets are at distance at most two from each other. The Min-Se...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2024-12-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/09728600.2024.2443910 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Let [Formula: see text] be a graph without any isolated vertices. A semipaired dominating set [Formula: see text] of G, is a dominating set of G, if D can be partitioned into cardinality 2 subsets such that the vertices in each of these subsets are at distance at most two from each other. The Min-Semi-PD problem is to compute a minimum cardinality semipaired dominating set of a given graph G. It is known that the decision version of the problem is NP-complete for bipartite graphs and split graphs. In this article, we resolve the complexity of the problem in two well studied graph classes, namely, AT-free graphs and planar graphs. We show that the decision version of the Min-Semi-PD problem remains NP-complete for planar graphs. On the positive side, we propose a polynomial-time exact algorithm for the Min-Semi-PD problem in AT-free graphs, but the complexity of the algorithm is quite high. So, in addition, we also give a linear-time constant factor approximation algorithm for the problem in AT-free graphs. |
|---|---|
| ISSN: | 0972-8600 2543-3474 |