Roman Domination on Acyclic Permutation Graphs (Journal of Informatics and Mathematical Sciences, 2017)
A function \(f : V→[0, 1, 2]\) is said to be Roman dominating function on a graph \(G=(V, E)\) if the function \(f\) satisfies the condition that every vertex \(u\) for which \(f(u)=0\) has at least one neighboring vertex \(v\) with \(f(v)=2\). The weight of a Roman dominating function is the value \(f(V)=\sum\limits_{v\in V}{f(v)}\). The Roman domination number of \(G\) is the minimum weight of a Roman dominating function and is denoted by \(γ_{R}(G)\). In this paper we study the Roman domination number on acyclic permutation graphs.