Turkish Journal of Mathematics and Computer Science

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

Konular:Matematik

DOI:10.47000/tjmcs.766711

Anahtar Kelimeler:Roman Domination,Roman graphs,Dominant differential graphs

Özet: 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$.

---