Dominación Romana, Dominación Potencial y Zero Forcing en grafos periplanos maximales

Ranilla Cortina, Sandra (2017). Dominación Romana, Dominación Potencial y Zero Forcing en grafos periplanos maximales. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Dominación Romana, Dominación Potencial y Zero Forcing en grafos periplanos maximales
Author/s:
  • Ranilla Cortina, Sandra
Contributor/s:
  • Hernández Peñalver, Gregorio
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2017
Subjects:
Freetext Keywords: Dominación Romana; Dominación Potencial; Zero Forcing; Grafo periplano maximal; Roman Domination; Power Domination; Zero Forcing; Maximal outerplanar graph
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (736kB) | Preview

Abstract

Algunos de los problemas más estudiados en Teoría de Grafos son aquellos que hacen ref- erencia al recubrimiento del grafo, siendo uno de los más clásicos el problema del conjunto dominante de un grafo. Un conjunto D de vértices de un grafo G se dice que es un conjunto dominante si cada vértice que no pertenece a D es adyacente a, al menos, un vértice del conjunto D. Parece entonces obvio preguntarse cuál es el mínimo cardinal de un conjunto dominante para un determinado grafo, es decir, determinar cuál es el número de dominación para un grafo G, que se denota como (Gamma) (G). Por otro lado, en 1979 Garey y Johnson en su libro Computers and Intractability: Guide to the Theory of NP-Completenss probaron que este problema es NP-completo. Desde que se estudió el problema de dominación por primera vez, se han ido desarrollando variantes de este en función del planteamiento del problema o la posibilidad de propagación del conjunto dominante. Primero, estudiaremos la Dominación Romana. Es un problema de estrategia militar, cuyo objetivo es defender un conjunto de regiones con el mínimo número de legiones posible, tal que al número de dominación romana se le denota por (Gamma)R(G). A continuación, veremos dos variantes en las cuales se puede propagar el conjunto dominante, la Dominación Potencial y el Zero Forcing. Bajo unas reglas de propagación, la idea es la misma, encontrar el conjunto D de cardinal mínimo necesario para dominar determinado grafo G, y que se denota por (Gamma)P (G) y Z(G) respectivamente. A lo largo de estos meses de trabajo, se han estudiado los resultados obtenidos hasta la fecha en estas variantes de dominación. Este estudio se ha llevado a cabo tanto desde el punto de vista combinatorio como algorítmico, y se ha restringido a un tipo particular de grafos, los grafos periplanos maximales, y denotados por su acrónimo en inglés como MOPs. Con este trabajo se pretende por un lado, recopilar aquellos resultados más significativos de la bibliografía en un artículo tipo "survey". Por otro lado, obtener nuevos resultados sobre la variantes del Zero Forcing para MOPs. Y también, resultados para el Zero Forcing Conexo para grafos uniciclos y cactus.---ABSTRACT---Some of the most studied problems in Graph Theory are those referring to the graph covering, being one the most famous the dominating set problem. A dominating set for a graph G = (V, A) is a subset D C V such that every vertex not in D is adjacent to at least one member of D. It seems obvious to wonder which is the minimum dominating set for a particular graph, that is, obtain what is known as the domination number for a graph G = (V, E), denoted by (Gamma)(G). Nevertheless, the problem of finding a minimum dominating set in a general graph has been shown by Garey and Johnson in 1979 in their book Computers and Intractability: Guide to the Theory of NP-Completenss to be NP-complete. Since the problem was first studied, many variants have been developed according to the problem description and how the graph can be dominated. First, we are going to study the Roman Domination problem. It's a classical problem in military strategy, whose aim is to defend a number of regions with the minimum legions as possible, such that the roman domination number is denoted by (Gamma)R(G). Then, we are going to study other two variants of the dominating set problem known as the Power Domination and the Zero Forcing. In these problems, there are some rules that propagate the dominating set. Following these propagation rules, the aim is to find the minimum cardinality of the dominating set D of a graph G, which is denoted respectively by (Gamma)P (G) and Z(G). Throughout these months, the results achieved about the variants of the dominating prob- lem for arbitrary graphs have been studied. This research has been formed not only from a combinatorial point of view but also from an algorithmic point of view, and has been restricted to a particular kind of graph, known as maximal outerplanar graphs and denoted by its acronym as MOPs. This project has a double purpose: on the one hand, it seeks to collect those results in the literature which have been observed to be more significant in a review paper or survey. On the other hand, it seeks to obtain new results for the Zero Forcing problem for MOPs and results for Connected Zero Forcing for unicycle graphs and cactus.

More information

Item ID: 47128
DC Identifier: http://oa.upm.es/47128/
OAI Identifier: oai:oa.upm.es:47128
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 04 Jul 2017 12:00
Last Modified: 04 Jul 2017 12:00
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM