A New Approach on Roman Graphs

Abstract

Let $G=(V,E)$ be a simple graphwith vertex set $V=V(G)$ andedge set $E=E(G)$. A Roman dominating function (RDF) on a graph $G$ is a function $f:Vrightarrow{0,1,2}$ satisfying the condition that every vertex $u$ for which $f(u)=0$ is adjacent to at least one vertex $v$ such that $f(v)=2$. The weight of $f$ is $omega(f)=Sigma_{vin V}f(v)$. The minimum weight of an RDF on $G$, $gamma_{R}(G)$, is called the Roman domination number of $G$. $gamma_{R}(G)leq 2gamma(G)$ where $gamma(G)$ denotes the domination number of $G$. A graph $G$ is called a Roman graph whenever $gamma_{R}(G)= 2gamma(G)$. On the other hand, the differential of $X$ is defined as $partial(X)=|B(X)|-|X|$ and the differential of a graph $G$, written $partial(G)$, is equal to $max{partial(X): Xsubseteq V}$. By using differential we provide a sufficient and necessary condition for the graphs to be Roman. We also modify the proof of a result on Roman trees. Finally we characterizethe large family of trees $T$ such that $partial(T)=n-gamma(T)-2$.