2015/02/26 by B. S. Panda, Panda, B. S., Arti Pandey +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1502.07718
openalex publication_date 2015/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G=(V,E), a set D⊆ V is called a disjunctive dominating set of G if for every vertex v∈ V∖ D, v is either adjacent to a vertex of D or has at least two vertices in D at distance 2 from it. The cardinality of a minimum disjunctive dominating set of G is called the disjunctive domination number of graph G, and is denoted by γ2d(G). The Minimum Disjunctive Domination Problem (MDDP) is to find a disjunctive dominating set of cardinality γ2d(G). Given a positive integer k and a graph G, the Disjunctive Domination Decision Problem (DDDP) is to decide whether G has a disjunctive dominating set of cardinality at most k. In this article, we first propose a linear time algorithm for MDDP in proper interval graphs. Next we tighten the NP-completeness of DDDP by showing that it remains NP-complete even in chordal graphs. We also propose a (ln(Δ2+Δ+2)+1)-approximation algorithm for MDDP in general graphs and prove that MDDP can not be approximated within (1-ε) ln(|V|) for any ε>0 unless NP ⊆ DTIME(|V|O(log log |V|)). Finally, we show that MDDP is APX-complete for bipartite graphs with maximum degree 3.