Abstract
A roman domination problem is quite a hot variant domination problem in recent years. In one graph G = (V, E), a roman domination function is a function f : V □ {0, 1, 2}, that each one vertex u with f(u) = 0 is adjacent to at least one vertex v with f(v) = 2, among them u and v belongs to V. The weight of a roman domination function f is the sum of the weight of V. A roman domination number of a graphs G is the smallest weight of the possible roman domination function f. When give one permutation graph, we can provide a polynomial algorithm (O(n5))to find out the roman domination number by using the method of dynamic programming. It checks all the possible order cross pairs. With regard to each order cross pair, we find out the best solution for it at that time. Finally we combine the solution to solve roman dominating function.