期刊
APPLIED MATHEMATICS AND COMPUTATION
卷 438, 期 -, 页码 -出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.amc.2022.127554
关键词
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, 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.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据