Independent Double Roman Domination in Graphs

For a graph G = ( V , E ) , a double Roman dominating function (DRDF) on G is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f ( v ) = 0 , then vertex v has at least two neighbors assigned 2 under f or one neighbor w with f ( w ) = 3 , and if f ( v ) = 1 , then vertex v has at leas...

Full description

Saved in:
Bibliographic Details
Published in:Bulletin of the Iranian Mathematical Society 2020-04, Vol.46 (2), p.543-555
Main Authors: Maimani, Hamidreza, Momeni, Mostafa, Nazari Moghaddam, Sakineh, Rahimi Mahid, Farhad, Sheikholeslami, Seyed Mahmoud
Format: Article
Language:English
Subjects:
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a graph G = ( V , E ) , a double Roman dominating function (DRDF) on G is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f ( v ) = 0 , then vertex v has at least two neighbors assigned 2 under f or one neighbor w with f ( w ) = 3 , and if f ( v ) = 1 , then vertex v has at least one neighbor w with f ( w ) ≥ 2 . A DRDF f is called an independent double Roman dominating function (IDRDF) if the set of vertices with positive weight is independent. The weight of an IDRDF is the sum f ( V ) = ∑ v ∈ V f ( v ) . The independent double Roman domination number i dR ( G ) is the minimum weight of an IDRDF on G . In this paper, we initiate the study of independent double Roman domination. We first show that the decision problem associated with i dR ( G ) is NP-complete for bipartite graphs and then we present some sharp bounds on the independent double Roman domination number.
ISSN:1017-060X
1735-8515
DOI:10.1007/s41980-019-00274-8