Outer independent Roman dominating functions in graphs

A Roman dominating function (RDF) on a graph G is a function satisfying the condition that every vertex u for which is adjacent to at least one vertex v for which . A function is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and is an independent set. The outer-independe...

Full description

Saved in:
Bibliographic Details
Published in:International journal of computer mathematics 2017-12, Vol.94 (12), p.2547-2557
Main Authors: Abdollahzadeh Ahangar, Hossein, Chellali, Mustapha, Samodivkin, Vladimir
Format: Article
Language:English
Subjects:
Graphs
Mathematical functions
Minimum weight
outer-independent Roman domination
Roman domination
Upper bounds
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:A Roman dominating function (RDF) on a graph G is a function satisfying the condition that every vertex u for which is adjacent to at least one vertex v for which . A function is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and is an independent set. The outer-independent Roman domination number is the minimum weight of an OIRDF on G. In this paper, we initiate the study of the outer-independent Roman domination number in graphs. We first show that determining the number is NP-complete for bipartite graphs. Then we present lower and upper bounds on . Moreover, we characterize graphs with small or large outer-independent Roman domination number.
ISSN:0020-7160
1029-0265
DOI:10.1080/00207160.2017.1301437