Conjunto dominante eterno

En teoría de grafos , un conjunto dominante eterno para un grafo G  =  ( V , E ) es un subconjunto D de V tal que D es un conjunto dominante en el que se ubican inicialmente guardias móviles (como máximo, un guardia puede ubicarse en cualquier vértice). El conjunto D debe ser tal que, para cualquier secuencia infinita de ataques que ocurran secuencialmente en los vértices, el conjunto D puede modificarse moviendo un guardia de un vértice adyacente al vértice atacado, siempre que el vértice atacado no tenga ningún guardia en el momento del ataque. La configuración de guardias después de cada ataque debe inducir un conjunto dominante. El número de dominación eterna , γ _∞ ( G ), es el número mínimo de vértices posible en el conjunto inicial D . Por ejemplo, el número de dominación eterna del ciclo en cinco vértices es tres.  

El problema del conjunto dominante eterno, también conocido como problema de dominación eterna o problema de seguridad eterna, puede interpretarse como un juego combinatorio entre dos jugadores que se turnan: un defensor, que elige el conjunto dominante inicial D y la guardia que enviará ante cada ataque que ocurra en un vértice sin guardia; y un atacante, que elige el vértice que atacará en su turno. El atacante gana si logra elegir un vértice para atacar de tal manera que no haya ninguna guardia en ese vértice ni en un vértice vecino; el defensor gana en caso contrario. En otras palabras, el atacante gana si logra atacar un vértice de tal manera que el ataque sea imposible de defender.

Como se señala en Klostermeyer y Mynhardt (2015b) , el problema del conjunto dominante eterno está relacionado con el problema del k -servidor en ciencias de la computación.

Motivado por problemas antiguos en defensa militar descritos en la serie de artículos de Arquilla y Fredricksen (1995) , ReVelle y Rosing (2000) y Stewart (1999) , el problema de la dominación eterna fue descrito inicialmente en 2004 en un artículo de Burger et al. (2004) . A esto le siguió la publicación de un artículo sobre dominación eterna por Goddard, Hedetniemi y Hedetniemi (2005) , que también introdujo una variación del problema llamada m -dominación eterna en la que todos los guardias pueden moverse a vértices adyacentes, si así lo desean, en respuesta a un ataque, siempre que un guardia se mueva al vértice atacado (suponiendo que no había un guardia en el vértice atacado; de lo contrario, ningún guardia necesita moverse). Posteriormente al artículo de Goddard, Hedetniemi y Hedetniemi (2005) , aparecieron varios artículos de otros autores en la literatura matemática. En estos trabajos posteriores, se propusieron varias variaciones adicionales del problema de dominación eterna, incluyendo el problema de cobertura de vértices eterna, el problema de conjuntos independientes eternos, conjuntos dominantes totales eternos, conjuntos dominantes conectados eternos y conjuntos dominantes eternos en el modelo de desalojo (este último modelo requiere que cuando ocurren ataques, un vértice con un guardia y el guardia deben moverse a un vértice vecino que no contenga ningún guardia, si existe alguno). Un artículo de revisión que describe muchos de los resultados sobre el problema de dominación eterna y muchas de las variaciones del problema se puede encontrar en Klostermeyer y Mynhardt (2015b) .

Sea G un grafo con n  ≥  1 vértices. Trivialmente, el número de dominación eterna es al menos el número de dominación γ( G ). En su artículo, Goddard, Hedetniemi y Hedetniemi demostraron que el número de dominación eterna es al menos el número de independencia de G y como máximo el número de cobertura de clique de G (el número de cobertura de clique de G es igual al número cromático del complemento de G ). Por lo tanto, el número de dominación eterna de G es igual al número de cobertura de clique de G para todos los grafos perfectos, debido al teorema del grafo perfecto . Se ha demostrado que el número de dominación eterna de G es igual al número de cobertura de clique de G para varias otras clases de grafos, como los grafos de arco circular (como se demostró en Regan (2007) ) y los grafos serie-paralelo (como se demostró en Anderson et al. (2007) ). Goddard, Hedetniemi y Hedetniemi también demostraron un gráfico en el que el número de dominación eterna del gráfico es menor que el número de cobertura de la camarilla.

Klostermeyer y MacGillivray (2007) demostraron que el número de dominación eterna de un grafo con número de independencia α es como máximo α ( α  +  1)/2. Goldwasser y Klostermeyer (2008) demostraron que existen infinitos grafos donde el número de dominación eterna es exactamente α ( α  +  1)/2.

Goddard, Hedetniemi y Hedetniemi demostraron que el número de dominación m- eterna , denotado γ ^m _∞ ( G ), es como máximo el número de independencia de G . Por lo tanto, los parámetros de dominación eterna encajan perfectamente en la famosa cadena de parámetros de dominación, véase ( Haynes, Hedetniemi y Slater 1998a ) , de la siguiente manera:

γ( GRAMO ) ≤ γ ^m _∞ ( GRAMO ) ≤ α( GRAMO ) ≤ γ _∞ ( GRAMO ) ≤ θ ( GRAMO )

donde θ ( G ) denota el número de cobertura de clique de G y γ _∞ ( G ) denota el número de dominación eterna.

Se demostró una cota superior de ⌈ n /2⌉ en γ ^m _∞ ( G ) para grafos con n vértices en Chambers, Kinnersly y Prince (2006) , ver también Klostermeyer y Mynhardt (2015b) .

El número de dominación m -eterna en grafos de cuadrícula ha atraído la atención, inspirado por la atención prestada al número de dominación de los grafos de cuadrícula, véase Haynes, Hedetniemi y Slater (1998a) y Goncalves et al. (2011) . El número de dominación m -eterna en grafos de cuadrícula fue estudiado por primera vez en Goldwasser, Klostermeyer y Mynhardt (2013) donde se demostró que

γ ^m _∞ = ⌈2 n /3⌉ para la cuadrícula de 2 por n con n  ≥  2

y

γ ^m _∞ ≤ ⌈8 n /9⌉ para cuadrículas de 3 por n .

Este último fue mejorado en Finbow, Messinger y van Bommel (2015) para

1 + ⌈4 norte /5⌉ ≤ γ ^metro _∞ ≤ 2 + ⌈4 norte /5⌉

cuando n ≥ 11. Este límite fue posteriormente mejorado ligeramente en Messinger y Delaney (2015) en algunos casos. Finalmente, los límites fueron cerrados en Finbow y van Bommel (2020) , donde se demostró que

γ ^m _∞ = ⌈(4 n +7)/5⌉ para n  ≥  22.

Los casos para cuadrículas de 4 por y cuadrículas de 5 por n fueron considerados en Beaton, Finbow y MacDonald (2013) y van Bommel y van Bommel (2016) , respectivamente.

Braga, de Souza y Lee (2015) demostraron que γ ^m _∞ = α para todos los grafos de intervalos propios y los mismos autores también demostraron, véase Braga, de Souza y Lee (2016) , que existe un grafo de Cayley para el cual el número de dominación m -eterna no es igual al número de dominación, contrariamente a la afirmación en Goddard, Hedetniemi y Hedetniemi (2005) .

La conjetura γ–θ afirma que, para cada grafo G ,${\displaystyle \gamma (G)=\gamma _{\infty }(G)}$si y solo si${\displaystyle \gamma (G)=\theta (G)}$, dónde${\displaystyle \theta (G)}$es el número de cobertura de la camarilla. ^{[ 1 ]} Dado que${\displaystyle \gamma (G)\leq \gamma _{\infty }(G)\leq \theta (G)}$, un contraejemplo sería precisamente un grafo G tal que${\displaystyle \gamma (G)=\gamma _{\infty }(G)<\theta (G)}$Según Klostermeyer y Mynhardt (2015b) , la existencia de tal grafo es una de las principales incógnitas. Klostermeyer y Mynhardt (2015a) demostraron que cualquier grafo de este tipo debe contener un triángulo y tener un grado máximo de vértice de al menos cuatro.

De forma similar a la conjetura de Vizing para conjuntos dominantes, no se sabe si para todos los grafos G y H

${\displaystyle \gamma _{\infty }(G,\Box ,H)\geq \gamma _{\infty }(G)\gamma _{\infty }(H).}$

Se sabe que la cota análoga no se cumple para todos los grafos G y H para el problema de dominación m -eterna, como se muestra en Klostermeyer y Mynhardt (2015a) .

Douglas West enumera dos preguntas fundamentales abiertas sobre la dominación eterna en:: si γ _∞ ( G ) es igual al número de cobertura de clique para todos los grafos planares G y si γ _∞ ( G ) puede ser acotado inferiormente por el número de Lovász , también conocido como la función theta de Lovász.

En el artículo de revisión de Klostermeyer y Mynhardt (2015b) se plantean otras cuestiones abiertas , incluidas muchas preguntas sobre las variaciones de los conjuntos dominantes eternos mencionados anteriormente.

• Anderson, M.; Barrientos, C.; Brigham, R.; Carrington, J.; Vitray, R.; Yellen, J. (2007), "Gráficos de demanda máxima para seguridad eterna" , J. Combin. Math. Combin. Comput. , 61 : 111–128.
• Arquilla, H.; Fredricksen, H. (1995), "Graphing an optimal grand strategy", Military Operations Research , 1 (3): 3– 17, doi : 10.5711/morj.1.3.3 , hdl : 10945/38438 , JSTOR 43940682 .
• Beaton, I.; Finbow, S.; MacDonald, J. (2013), "Problema del conjunto de dominación eterna de cuadrículas", J. Combin. Math. Combin. Comput. , 85 : 33– 38.
• Braga, A.; de Souza, C.; Lee, O. (2015), "El problema del conjunto dominante eterno para grafos de intervalos propios", Information Processing Letters , 115 ( 6–8 ): 582–587 , doi : 10.1016/j.ipl.2015.02.004.
• Braga, A.; de Souza, C.; Lee, O. (2016), "Una nota sobre el artículo "Seguridad eterna en grafos" de Goddard, Hedetniemi y Hedetniemi (2005)", Journal of Combinatorial Mathematics and Combinatorial Computing , 96 : 13–22.
• Hamburguesa, AP; Cockayne, EJ; Grundlingh, WR; Mynhardt, CM; van Vuuren, J.; Winterbach, W. (2004), "Dominación del orden infinito en gráficos", J. Combin. Matemáticas. Combinar. Computadora. , 50 : 179-194​.
• Chambers, E.; Kinnersly, B.; Prince, N. (2006), "Seguridad eterna móvil en grafos" , Manuscrito inédito , archivado del original el 30 de septiembre de 2015 , consultado el 21 de febrero de 2015..
• Finbow, S.; Messinger, ME.; van Bommel, M. (2015), "Dominación eterna en cuadrículas 3 xn", Australas. J. Combin. , 61 : 156– 174.
• Finbow, S.; van Bommel, MF (2020), "El número de dominación eterna para grafos de cuadrícula de 3 x n", Australas. J. Combin. , 71 : 1– 23.
• Goddard, Wayne; Hedetniemi, Sandra M.; Hedetniemi, Stephen T. (enero de 2005). "Seguridad eterna en grafos" . Journal of Combinatorial Mathematics and Combinatorial Computing . 52 .
• Goldwasser, J.; Klostermeyer, W. (2008), "Límites ajustados para conjuntos dominantes eternos en grafos", Discrete Math. , 308 (12): 2589– 2593, doi : 10.1016/j.disc.2007.06.005.
• Goldwasser, J.; Klostermeyer, W.; Mynhardt, C. (2013), "Protección eterna en grafos de cuadrícula", Utilitas Math. , 91 : 47– 64.
• Goncalves, D.; Pinlou, A.; Rao, M.; Thomasse, S. (2011), "El número de dominación de las cuadrículas", SIAM Journal on Discrete Mathematics , 25 (3): 1443– 1453, arXiv : 1102.5206 , doi : 10.1137/11082574.
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentos de dominación en grafos , Marcel Dekker, ISBN 0-8247-0033-3, OCLC 37903553 .
• Klostermeyer, W.; MacGillivray, G. (2007), "Seguridad eterna en grafos de número de independencia fijo", J. Combin. Math. Combin. Comput. , 63 : 97– 101.
• Klostermeyer, W.; Mynhardt, C. (2015a), "Dominación, dominación eterna y cobertura de cliques", Discuss. Math. Graph Theory , 35 (2): 283, arXiv : 1407.5235 , doi : 10.7151/dmgt.1799.
• Klostermeyer, W.; Mynhardt, C. (2015b), "Protegiendo un grafo con guardianes móviles", Applicable Analysis and Discrete Mathematics , 10 : 21, arXiv : 1407.5228 , doi : 10.2298/aadm151109021k.
• Messinger, ME.; Delaney, A. (2015), Cerrando la brecha: Dominación eterna en cuadrículas 3 xn.
• Regan, F. (2007), Variantes dinámicas de dominación e independencia en grafos , Universidad Rheinischen Friedrich-Wilhlems.
• ReVelle, C. (2007), "¿Puedes proteger el Imperio Romano?", Revista Johns Hopkins , 2.
• ReVelle, C.; Rosing, K. (2000), "Defendens Imperium Romanum: Un problema clásico en estrategia militar", Amer. Math. Monthly , 107 (7): 585– 594, doi : 10.2307/2589113 , JSTOR 2589113 .
• Stewart, I. (1999), "¡Defiendan el Imperio Romano!", Scientific American , 281 (6): 136– 138, Bibcode : 1999SciAm.281f.136S , doi : 10.1038/scientificamerican1299-136.
• van Bommel, C.; van Bommel, M. (2016), "Número de dominación eterna de cuadrículas de 5 xn", J. Combin. Matemáticas. Combinar. Computación , 97 : 83– 102.