Efficient algorithms for Roman domination on some classes of graphs

A Roman dominating function of a graph G=(V,E)G=(V,E) is a function f:V→{0,1,2}f:V→{0,1,2} such that every vertex xx with f(x)=0f(x)=0 is adjacent to at least one vertex yy with f(y)=2f(y)=2. The weight of a Roman dominating function is defined to be f(V)=∑x∈Vf(x)f(V)=∑x∈Vf(x), and the minimum weight of a Roman dominating function on a graph GG is called the Roman domination number of GG. In this paper we first answer an open question mentioned in [E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11–22] by showing that the Roman domination number of an interval graph can be computed in linear time. We then show that the Roman domination number of a cograph (and a graph with bounded cliquewidth) can be computed in linear time. As a by-product, we give a characterization of Roman cographs. It leads to a linear-time algorithm for recognizing Roman cographs. Finally, we show that there are polynomial-time algorithms for computing the Roman domination numbers of AT-free graphs and graphs with a dd-octopus.