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.

Descripción

Título: Dominación Romana, Dominación Potencial y Zero Forcing en grafos periplanos maximales
Autor/es:
  • Ranilla Cortina, Sandra
Director/es:
  • Hernández Peñalver, Gregorio
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Matemáticas e Informática
Fecha: Junio 2017
Materias:
Palabras Clave Informales: Dominación Romana; Dominación Potencial; Zero Forcing; Grafo periplano maximal; Roman Domination; Power Domination; Zero Forcing; Maximal outerplanar graph
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (736kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 47128
Identificador DC: http://oa.upm.es/47128/
Identificador OAI: oai:oa.upm.es:47128
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 04 Jul 2017 12:00
Ultima Modificación: 04 Jul 2017 12:00
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM