## Abstract

In a graph G=(V,E) without an isolated vertex, a dominating set D⊆V is a paired dominating set if the graph G[D] induced by D has a perfect matching. Further, a set D⊆V is a disjunctive dominating set of G if for each vertex v∈V, either N_{G}[v]∩D≠∅ or there are at least two vertices in D whose distance from v is two in G. We introduce the notion of paired disjunctive domination in graphs. A disjunctive dominating set D⊆V in the graph G is a paired disjunctive dominating set if G[D] has a perfect matching. The minimum cardinality of a paired disjunctive dominating set of G is the paired disjunctive domination number, denoted by γ_{pr}^{d}(G). In this article, we compute the exact value of γ_{pr}^{d}(G) when G is a path, cycle, cograph, chain graph, and split graph. We prove that the decision version of the problem is NP-complete for planar graphs, bipartite graphs, and chordal graphs and design a polynomial-time algorithm to compute a minimum cardinality paired disjunctive dominating set in interval graphs. Further, we obtain lower and upper bounds on the approximation ratio of the problem and proved that the problem is APX-complete for the graphs with maximum degree 4.

Original language | English |
---|---|

Article number | 113990 |

Journal | Theoretical Computer Science |

Volume | 966-967 |

DOIs | |

Publication status | Published - 26 Jul 2023 |

## Keywords

- Approximation algorithm
- Graph algorithms
- Interval graphs
- NP-completeness
- Paired disjunctive domination
- Paired domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science