On outer-convex Roman dominating function in graphs

Abstract

Let \(G = (V(G), E(G))\) be a connected graph and let \(\phi:V(G)\rightarrow \{0,1,2\}\) be a Roman dominating function (RDF) on \(G\). For each \(j \in \{0, 1, 2\}\), let \(V_j=\{x \in V(G): \phi(x)=j\}\). Then \(\phi\) can be represented as \(\phi=(V_0, V_1, V_2)\). A function \(\phi\) is an \textit{outer-convex Roman dominating function} (OConRDF) on \(G\) if for each \(v\in V_0\), there exists \(u\in V_2\) such that \(uv\in E(G)\) and \(V_0\) is a convex set in \(G\). The weight of OConRDF \(\phi\) is denoted by \(\widetilde{\omega}_G^{conR}(\phi)\) and is defined as \(\widetilde{\omega}_G^{conR}(\phi)=\sum_{x \in V(G)}\phi(x)\), that is, \(\widetilde{\omega}_G^{conR}(\phi)=|V_1|+2|V_2|\). Additionally, the outer-convex Roman domination number of \(G\) is denoted by \(\widetilde{\gamma}_{conR}(G)\) and is defined as the minimum weight of an OConRDF on \(G\), that is, \(\widetilde{\gamma}_{conR}(G)=min\{\widetilde{\omega}_G^{conR}(\phi): \phi \ is \ an \ \text{OConRDF} \ on \ G \}\). Furthermore, any OConRDF \(\phi\) on \(G\) with \(\widetilde{\omega}_{G}^{conR}(\phi)= \widetilde{\gamma}_{conR}(G)\) is called a \(\widetilde{\gamma}_{conR}\)-function on \(G\). This paper introduces a new parameter of a Roman dominating function in graphs and discusses some theoretical properties, including bounds, the realization problem, and characterizations.