RT journal article
T1 Restrained condition on double Roman dominating functions
A1 Samadi, Babak
A1 Soltankhah, Narin
A1 Abdollahzadeh Ahangar, H.
A1 Chellali, Mustaph
A1 Mojdeh, D. Ali
A1 Sheikholeslami, Seyed Mahmoud
A1 Valenzuela Tripodoro, Juan Carlos
A2 Matemáticas
K1 Roman domination
K1 Restrained domination
K1 Double domination
K1 Restrained double domination
AB 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 Tof 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.
PB Elsevier
SN 0096-3003
YR 2023
FD 2023-02-01
LK http://hdl.handle.net/10498/30802
UL http://hdl.handle.net/10498/30802
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 12-nov-2026