Let G be a simple, undirected graph. A function g : V(G) -> {0, 1, 2, 3} having the property that Sigma(v is an element of NG(u))g(v) >= 3, if g(u) = 0, and Sigma(v is an element of NG(u))g(v) >= 2, if g(u) =...
详细信息
Let G be a simple, undirected graph. A function g : V(G) -> {0, 1, 2, 3} having the property that Sigma(v is an element of NG(u))g(v) >= 3, if g(u) = 0, and Sigma(v is an element of NG(u))g(v) >= 2, if g(u) = 1 for any vertex u is an element of G, where N-G(u) is the set of vertices adjacent to u in G, is called a Roman domination-dominating function (R3DF) of G. The weight of a R3DF g is the sum g(V)= Sigma(v is an element of V)g(v). The minimum weight of a R3DF is called the Roman domination-domination number and is denoted by gamma({R3})(G). Given a graph G and a positive integer k, the Roman domination-domination problem (R3DP) is to check whether G has a R3DF of weight at most k. In this paper, first we show that the R3DP is NP-complete for chordal graphs, planar graphs and for two subclasses of bipartite graphs namely, star convex bipartite graphs and comb convex bipartite graphs. The minimum Roman domination-domination problem (MR3DP) is to find a R3DF of minimum weight in the input graph. We show that MR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs. We propose a 3(1 + ln(Delta - 1))-approximation algorithm for the MR3DP, where Delta is the maximum degree of G and show that the MR3DP problem cannot be approximated within (1 - epsilon)ln|V| for any epsilon > 0 unless NP subset of DTIME(|V|(O(loglog|V|))). Next, we show that the MR3DP problem is APX-complete for graphs with maximum degree 4. We also show that the domination and Roman domination-domination problems are not equivalent in computational complexity aspects. Finally, an ILP formulation for MR3DP is proposed.
暂无评论