查看文章

A Roman dominating function of a graph G = (V,E) is a function f : V → {0,1,2} such that every vertex x with f(x) = 0 is adjacent to at least one vertex y with f(y) = 2. The weight of a Roman dominating function is defined to be f(V) = ∑ _x ∈ V f(x), and the minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G.

In this paper we answer an open problem mentioned in [2] by showing that the Roman domination number of an interval graph can be computed in linear time. We also show that the Roman domination number of a cograph can be computed in linear time. Besides, we show that there are polynomial time algorithms for computing the Roman domination numbers of AT-free graphs and graphs with a d-octopus.