Outer independent Roman dominating functions in graphs

ABSTRACT

A Roman dominating function (RDF) on a graph G is a function $f:V\left(G\right)\to \{0,1,2\}$ satisfying the condition that every vertex u for which $f\left(u\right)=0$ is adjacent to at least one vertex v for which $f\left(v\right)=2$. A function $f:V\left(G\right)\to \{0,1,2\}$ is an outer-independent Roman dominating function (OIRDF) on G if f is an RDF and $V_0$ is an independent set. The outer-independent Roman domination number ${\gamma }_{\mathrm{oiR}}\left(G\right)$ 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 ${\gamma }_{\mathrm{oiR}}\left(G\right)$ is NP-complete for bipartite graphs. Then we present lower and upper bounds on ${\gamma }_{\mathrm{oiR}}\left(G\right)$. Moreover, we characterize graphs with small or large outer-independent Roman domination number.

KEYWORDS:

• Roman domination
• outer-independent Roman domination

2000 AMS Subject Classification:

• 05C69

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.