Número de dominação romana em grafos

Abstract

In a Roman domination of a graph, vertices are assigned a value from {0,1,2} in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. In this dissertation, we show the history of the problem and prove that the Roman domination number is NP-Complete even for induced subgraphs of grids and it is APX-hard even for bipartite graphs with maximum degree 4. We also prove that the Roman domination number is fixed parameter tractable for graphs with bounded local treewidth, as graphs with bounded maximum degree or bounded genus (like planar graphs or toroidal graphs). We also obtain complexity results when we consider digraphs as an input for the problem such as bipartite tournaments and planar digraphs.