Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10609/122346
Título : Protection of Graphs. Generic results with emphasis on Cartesian and Lexicographic product of graphs
Autoría: Valveny Juncosa, Magdalena
Tutor: Rodriguez Velazquez, Juan Alberto  
Resumen : Suponga que una o más entidades están ubicadas en algunos de los vértices de un gráfico G y que una entidad en un vértice puede resolver un problema en cualquier vértice en su vecindad cerrada. De manera informal, decimos que G está protegido bajo una ubicación determinada de entidades si existe al menos una entidad disponible para manejar un problema en cualquier vértice. Cockayne y col. [Boletín del Instituto de Combinatoria y sus Aplicaciones 39 (2003) 87 {100] propuso cuatro propiedades de tales funciones bajo las cuales todo el gráfico puede protegerse de acuerdo con una determinada estrategia. En cada caso, el parámetro de interés será el peso mínimo de una función en la subclase (número mínimo de entidades utilizadas). En este trabajo, obtenemos fórmulas cerradas y límites estrechos para dos de estos tipos de protección: número de dominación romana débil y número de dominación segura; centrándose en gráficos de productos lexicográficos y cartesianos en términos de invariantes de los gráficos de factores involucrados en el producto. Se muestra que el problema de calcular el número de dominación romana débil (Henning y Hedetniemi [Discrete Math. 266 (2003) 239-251]) y el número de dominación segura (Boumediene Merouane y Chellali [Inform. Process. Lett. 115 (10)) (2015) 786 {790.]) Es NP-Hard, incluso cuando se restringe a gráficos bipartitos o cordales. Esto sugiere encontrar el número de dominación para clases especiales de gráficos u obtener buenos límites en este invariante.
Palabras clave : gráficos
protección de gráficos
dominación romana débil
dominación segura
producto lexicográfico de gráficos
producto cartesiano de gráficos
Tipo de documento: info:eu-repo/semantics/report
Fecha de publicación : 13-sep-2020
Licencia de publicación: http://creativecommons.org/licenses/by-nc-nd/3.0/es/  
Aparece en las colecciones: Treballs finals de carrera, treballs de recerca, etc.

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
mvalvenyTFM0920memory.pdfMemory of TFM644,4 kBAdobe PDFVista previa
Visualizar/Abrir