A New Approach on Roman Graphs

Authors : Doost Ali MOJDEH, İman MASOUMİ, Ali PARSİAN

Pages : 6-13

Doi:10.47000/tjmcs.766711

View : 15 | Download : 6

Publication Date : 2021-06-30

Article Type : Research Paper

Abstract :Let $G=insert ignore into journalissuearticles values(V,E);$ be a simple graph with vertex set $V=Vinsert ignore into journalissuearticles values(G);$ and edge set $E=Einsert ignore into journalissuearticles values(G);$. A Roman dominating function insert ignore into journalissuearticles values(RDF); on a graph $G$ is a function $f:V\rightarrow\{0,1,2\}$ satisfying the condition that every vertex $u$ for which $finsert ignore into journalissuearticles values(u);=0$ is adjacent to at least one vertex $v$ such that $finsert ignore into journalissuearticles values(v);=2$. The weight of $f$ is $\omegainsert ignore into journalissuearticles values(f);=\Sigma_{v\in V}finsert ignore into journalissuearticles values(v);$. The minimum weight of an RDF on $G$, $\gamma_{R}insert ignore into journalissuearticles values(G);$, is called the Roman domination number of $G$. $\gamma_{R}insert ignore into journalissuearticles values(G);\leq 2\gammainsert ignore into journalissuearticles values(G);$ where $\gammainsert ignore into journalissuearticles values(G);$ denotes the domination number of $G$. A graph $G$ is called a Roman graph whenever $\gamma_{R}insert ignore into journalissuearticles values(G);= 2\gammainsert ignore into journalissuearticles values(G);$. On the other hand, the differential of $X$ is defined as $\partialinsert ignore into journalissuearticles values(X);=|Binsert ignore into journalissuearticles values(X);|-|X|$ and the differential of a graph $G$, written $\partialinsert ignore into journalissuearticles values(G);$, is equal to $max\{\partialinsert ignore into journalissuearticles values(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 $\partialinsert ignore into journalissuearticles values(T);=n-\gammainsert ignore into journalissuearticles values(T);-2$.
Keywords : Roman Domination, Roman graphs, dominant differential graphs