The Roman Domination Problem on Grid Graphs

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.

La Dominazione è un'area della ricerca nella teoria dei grafi in rapida evoluzione. Questa dissertazione si propone di studiare il Problema della Dominazione Romana: introdotto di recente, questo problema ha alcune interessanti applicazioni nel mondo reale, quali le strategie militari e lo studio delle reti senza fili. Dato un grafo non orientato, una Funzione di Dominazione Romana è una funzione che etichetta i vertici con un numero intero compreso tra 0, 1, 2, e che inoltre soddisfa la seguente condizione: ogni vertice etichettato 0 deve essere adiacente ad almeno un vertice etichettato 2. Il peso di una Funzione di Dominazione Romana è la somma di tutte le etichette, e il peso minimo è detto Numero di Dominazione Romana. Il Problema della Dominazione Romana è proprio quello di trovare tali numero e funzione. Dopo aver elencato alcuni risultati salienti, studieremo il Problema della Dominazione Romana restringendo il campo ai grafi a griglia, cioè grafi che, quando rappresentati su di un Piano Euclideo, formano una specifica copertura regolare. Il nostro obbiettivo è quello di trovare un algoritmo che possa trovare una soluzione esatta per tutti i grafi a griglia, e per fare questo presentiamo alcuni risultati notevoli: proveremo un limite inferiore migliore al Numero di Dominazione Romana e presenteremo un limite superiore che migliora il limite precedente e che noi congetturiamo sia il Numero di Dominazione Romana per molti, se non tutti, i grafi a griglia.