Algorithmic aspects of b-disjunctive domination in graphs

For a fixed integer (b>1), a set (Dsubseteq V) is called a b-disjunctive dominating set of the graph (G=(V,E)) if for every vertex (vin V{setminus }D), v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The Minimum b-Disjunctive Domination Problem (MbDDP) is to find a b-disjunctive dominating set of minimum cardinality. The cardinality of a minimum b-disjunctive dominating set of G is called the b-disjunctive domination number of G, and is denoted by (gamma _{b}^{d}(G)). Given a positive integer k and a graph G, the b-Disjunctive Domination Decision Problem (bDDDP) is to decide whether G has a b-disjunctive dominating set of cardinality at most k. In this paper, we first show that for a proper interval graph G, (gamma _{b}^{d}(G)) is equal to (gamma (G)), the domination number of G for (b ge 3) and observe that (gamma _{b}^{d}(G)) need not be equal to (gamma (G)) for (b=2). We then propose a polynomial time algorithm to compute a minimum cardinality b-disjunctive dominating set of a proper interval graph for (b=2). Next we tighten the NP-completeness of bDDDP by showing that it remains NP-complete even in chordal graphs. We also propose a ((ln ({varDelta }^{2}+(b-1){varDelta }+b)+1))-approximation algorithm for MbDDP, where ({varDelta }) is the maximum degree of input graph (G=(V,E)) and prove that MbDDP cannot be approximated within ((1-epsilon ) ln (|V|)) for any (epsilon >0) unless NP (subseteq ) DTIME((|V|^{O(log log |V|)})). Finally, we show that MbDDP is APX-complete for bipartite graphs with maximum degree (max {b,4}).