## Abstract

Given a graph G= (V, E) , a function f: V⟶ { 0 , 1 , 2 , 3 } is called a double Roman dominating function on G if (i) for every v∈ V with f(v) = 0 , there are at least two neighbors of v that are assigned 2 under f or at least a neighbor of v that is assigned 3 under f, and (ii) for every vertex v with f(v) = 1 , there is at least one neighbor w of v with f(w) ≥ 2. The weight of a double Roman dominating function f is f(V) = ∑ _{u} _{∈} _{V}f(u). The double Roman domination number of G, denoted by γ_{dR}(G) is the minimum weight of a double Roman dominating function on G. For a graph G= (V, E) , Min-Double-RDF is to find a double Roman dominating function f with f(V) = γ_{dR}(G). The decision version of Min-Double-RDF is shown to be NP-complete for chordal graphs and bipartite graphs. In this paper, we first strengthen the known NP-completeness of the decision version of Min-Double-RDF by showing that the decision version of Min-Double-RDF remains NP-complete for undirected path graphs, chordal bipartite graphs, and circle graphs. We then present linear time algorithms for computing the double Roman domination number in proper interval graphs and block graphs. We then discuss on the approximability of Min-Double-RDF and present a 2-approximation algorithm in 3-regular bipartite graphs.

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

Pages (from-to) | 90-114 |

Number of pages | 25 |

Journal | Journal of Combinatorial Optimization |

Volume | 39 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Jan 2020 |

## Keywords

- Domination
- Double Roman domination
- NP-complete
- Polynomial time algorithm
- Roman domination

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics