ABSTRACT
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.
2000 AMS Subject Classification:
Acknowledgements
The authors are grateful to anonymous referees for their remarks and suggestions that helped improve the manuscript. H. Abdollahzadeh Ahangar acknowledge Babol Noshirvani University of Technology, Iran for a research grant.
Disclosure statement
No potential conflict of interest was reported by the authors.