ArchivIA Università degli Studi di Catania

ArchivIA - Archivio istituzionale dell'Universita' di Catania >
Tesi >
Tesi di dottorato >
Area 01 - Scienze matematiche e informatiche >

Utilizza questo identificativo per citare o creare un link a questo documento:

Data: 26-feb-2014
Autori: Curro', Vincenzo
Titolo: 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.
InArea 01 - Scienze matematiche e informatiche

Full text:

File Descrizione DimensioniFormatoConsultabilità
CRRVCN81P12F206T-CurroThesis.pdfCurroPhDThesis1,11 MBAdobe PDFVisualizza/apri

Tutti i documenti archiviati in ArchivIA sono protetti da copyright. Tutti i diritti riservati.

Segnala questo record su




Stumble it!



  Browser supportati Firefox 3+, Internet Explorer 7+, Google Chrome, Safari

ICT Support, development & maintenance are provided by the AePIC team @ CILEA. Powered on DSpace Software.