Restrained condition on double Roman dominating functions

We continue the study of restrained double Roman domination in graphs. For a graph G = (V (G), E(G)), a double Roman dominating function fis called a restrained double Roman dominating function (RDRD function) if the subgraph induced by {v is an element of V (G) broken vertical bar f(v) = 0} has no isolated vertices. The restrained double Roman domination number (RDRD number) gamma(rdR)(G) is the minimum weight Sigma(v is an element of V(G)) f(v) taken over all RDRD functions of G. We first prove that the problem of computing gamma(rdR) 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 gamma(rdR) and some wellknown parameters such as restrained domination number gamma(r), domination number gamma or restrained Roman domination number gamma(rR) are investigated in this paper by bounding.rdR from below and above involving gamma(r), gamma or gamma(rR) for general graphs, respectively. We prove that gamma(rdR) (T) = n + 2 for any tree T not equal K-1,K-n-1 of order n >= 2 and characterize the family of all trees attaining the lower bound. The characterization of graphs with small RDRD numbers is given in this paper. (C) 2022 Elsevier Inc. All rights reserved.

Automated summary

We continue the study of restrained double Roman domination in graphs, defining a new function and number and investigating their relationships with other parameters. We prove the complexity of computing the restrained double Roman domination number and provide solvable cases in linear time, as well as characterizing some graph families.