مشخصات پژوهش

عنوان	Restrained condition on double Roman dominating functions
نوع پژوهش	مقاله چاپ شده
کلیدواژه‌ها	Restrained double Roman domination, Roman domination, NP-hard, Tree, Planar graph, Bounded clique-width graph, Restrained domination number, Domination number.
چکیده	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.
پژوهشگران	جی.سی والنزوئلا-تری پودورو (نفر ششم به بعد)، محمود شیخ الاسلامی (نفر ششم به بعد)، دوستعلی مژده (نفر پنجم)، مصطفی شلالی (نفر چهارم)، حسین عبدله زاده آهنگر (نفر سوم)، نسرین سلطانخواه (نفر دوم)، بابک صمدی (نفر اول)