|
Title
|
Restrained condition on double Roman dominating functions
|
|
Type
|
JournalPaper
|
|
Keywords
|
Restrained double Roman domination, Roman domination, NP-hard, Tree, Planar graph, Bounded clique-width graph, Restrained domination number, Domination number.
|
|
Abstract
|
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 ∈ V (G ) | f(v ) = 0 } has no isolated vertices. The restrained double Roman domination number (RDRD number) γrdR (G ) is the minimum weight v ∈ V(G ) f(v ) taken over all RDRD functions of G . We first prove that the problem of computing γ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 γrdR and some well- known parameters such as restrained domination number γr , domination number γor re- strained Roman domination number γrR are investigated in this paper by bounding γrdR from below and above involving γr , γor γrR for general graphs, respectively. We prove that γrdR (T ) ≥n + 2 for any tree T = K 1 ,n −1 of order n ≥2 and characterize the family of all trees attaining the lower bound. The characterization of graphs with small RDRD num- bers is given in this paper.
|
|
Researchers
|
J.C. Valenzuela-Tripodoro (Not In First Six Researchers), Mahmood Sheikholeslami (Not In First Six Researchers), Doost Ali Mojdeh (Fifth Researcher), Mustapha Chellali (Fourth Researcher), Hossein ABDOLLAHZADEH AHANGAR (Third Researcher), Nasrin Soltankhah (Second Researcher), Babak Samadi (First Researcher)
|