June 10, 2023
Doost Ali Mojdeh

Doost Ali Mojdeh

Degree: Professor
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Education: Ph.D in Mathematics (Graph Theory and Combinatorics)
Phone: 011-35302448
Faculty: Faculty of Mathematical Sciences


Title A New Approach on Roman Graphs
Type Article
Roman domination, Roman graphs, dominant differential graphs
Journal Turkish Journal of Mathematics and Computer Science
DOI 10.47000/tjmcs.766711
Researchers Doost Ali Mojdeh (First researcher) , Iman Masoumi (Second researcher) , Ali Parsian (Third researcher)


Let $G=(V,E)$ be a simple graph with vertex set $V=V(G)$ and edge set $E=E(G)$. A Roman dominating function (RDF) on a graph $G$ is a function $f:V\rightarrow\{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_{v\in 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 2\gamma(G)$ where $\gamma(G)$ denotes the domination number of $G$. A graph $G$ is called a Roman graph whenever $\gamma_{R}(G)= 2\gamma(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): X\subseteq 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 characterize the large family of trees $T$ such that $\partial(T)=n-\gamma(T)-2$.