The Roman Domination Problem on Grid Graphs

Abstract

Domination is a rapidly developing area of research in graph theory. This dissertation focuses on the Roman Domination Problem; it was introduced quite recently and has some interesting applications in real world problems such military strategies and wireless networking.

Given a graph, a Roman Dominating Function is a function that labels the vertices of the graph with an integer between 0, 1, 2, satisfying the condition that every vertex labeled by 0 is adjacent to at least one vertex labeled by 2. The weight of a Roman Dominating Function is the sum of all the labels, and the minimum weight is called the Roman Domination Number. The Roman Domination Problem is to find such number and function.

In this dissertation we study the Roman Domination Problem when restricted to the class of grid graphs, i.e. graphs that, when drawn on an Euclidean Plane, form a specific regular tiling. A review of well--known results is given, and new results are presented. We aimed to find an algorithm that can find an exact solution for all the grid graphs, and, to do so, we present some important results: we prove a better lower-bound and present an upper-bound on the Roman Domination Number which improves the previous one and, we conjecture, is the Roman Domination Number for many, if not all, grid graphs.