Restrained condition on double Roman dominating functions

Abstract

We continue the study of restrained double Roman domination in graphs. For a graph G=(V,E) a double Roman dominating function is called a restrained double Roman dominating function (RDRD function) if the subgraph induced by the set of vertices labeled with a 0 has no isolated vertices. The restrained double Roman domination number (RDRD number) is the minimum weight taken over all RDRD functions of G. We first prove that the problem of computing is NP-hard even for planar graphs, but it is solvable in linear time when restricted to bounded clique-width graphs such as trees, cographs, and distance-hereditary graphs. Relationships between this new domination parameter and some well-known parameters such as restrained domination number, domination number or restrained Roman domination number are investigated in this paper. We prove that this parameter is bound by n+2 for any tree T of order n and we also characterize the family of all trees attaining the lower bound. The characterization of graphs with small RDRD numbers is given in this paper.