The Roman Domination Problem on Grid Graphs

The Roman Domination Problem is a combinatorial optmization problem defined over undirected graphs, whose decisional version has been proven to be NP-complete. In this paper we study the problem when restricted to the class of grid graphs. We derive an improved lower-bound and define and then discuss a general schema to produce good coverings for the Roman Domination Problem over grid graphs and finally present an upper-bound on the Roman Domination Number, derived from such schema, which improves the previous upper-bound and, we conjecture, is the RDN for many of the grid graphs.