On Efficiently Roman Dominatable Graphs

Abstract

A $(2,2)$ packing on a graph $G$ is a function $f:V(G)\to \{0,1,2\}$ with $f(N[v])\le 2$ for all $v\in V(G)$. For a function $f:V(G)\to \{0,1,2\}$, the Roman influence of $f$, denoted by $I_R(f)$, is defined to be $I_R(f)=(|V_1|+|V_2|)+\sum _{v\in V_2}deg(v)$. The efficient Roman domination number of $G$, denoted by $F_R(G)$, is defined to be the maximum of $I_R(f)$ such that $f$ is a $(2,2)$-packing. That is, $F_R(G)=\text{max}\{I_R(f):f\text{ is a }(2,2)-packing\}$. A $(2,2)$-packing $F_R(G)$ with $F_R(G)=I_R(f)$ is called an $F_R(G)$-function. A graph $G$ is said to be efficiently Roman dominatable if $F_R(G)=n$, and when $F_R(G)=n$, an $F_R(G)$-function is called an efficient Roman dominating function. In this paper, we focus our study on certain graphs which are efficiently Roman dominatable. We characterize the class of $2\times m$ and $3\times m$ grid graphs, trees, unicyclic graphs, and split graphs which are efficiently Roman dominatable.