A characterization of locating Roman domination edge critical graphs

Document Type : Original paper


1 Babol Noshirvani University of Technology

2 Amirkabir University of Technology


A Roman dominating function (or just \textit{RDF}) on a graph $G =(V, E)$ is a function $f: V \longrightarrow \{0, 1, 2\}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$. The weight of an \textit{RDF} $f$ is the value $f(V)=\sum_{u \in {V}}f(u)$. An \textit{RDF} $f$ can be represented as $f=(V_0,V_1,V_2)$, where $V_i=\{v\in V:f(v)=i\}$ for $i=0,1,2$. An \textit{RDF} $f=(V_0,V_1,V_2)$ is called a locating Roman dominating function (or just \textit{L\textit{RDF}}) if $N(u)\cap V_2\neq N(v)\cap V_2$ for any pair $u,v$ of distinct vertices of $V_0$. The locating-Roman domination number $\gamma_R^L(G)$ is the minimum weight of an \textit{L\textit{RDF}} of $G$. A graph $G$ is said to be a locating Roman domination edge  critical graph, or just $\gamma_R^L$-edge critical graph, if $\gamma_R^L(G-e)>\gamma_R^L(G)$ for all $e\in E$. The purpose of this paper is to characterize the class of $\gamma_R^L$-edge critical graphs.


Main Subjects