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.pdf | Memory of TFM | 644,4 kB | Adobe PDF | Visualizar/Abrir |
Comparte:
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons