Alumna: Carolina Lucía Gonzalez
Directora: Gabriela Argiroffo
Aula: 2

Resumen:

Consideremos el siguiente algoritmo goloso para encontrar un conjunto dominante: empezamos eligiendo un vértice cualquiera y luego, en cada paso, agregamos un vértice que domine algún vértice que no haya sido dominado previamente. Esto genera una sucesión de vértices que en su conjunto dominan al grafo. Si tenemos suerte, este algoritmo puede encontrar un conjunto dominante mínimo. Pero ¿qué ocurre en el peor caso? ¿cuál es la mayor cantidad de vértices que puede tener una sucesión de este estilo?
Estas preguntas dieron lugar a la llamada dominación Grundy, introducida recientemente en [1], donde también se demuestra que el problema de decisión asociado es NP-completo incluso en grafos cordales.

El objetivo de este trabajo es hallar familias de grafos donde el problema de dominación Grundy sea tratable. En este sentido, se obtuvieron algoritmos polinomiales que permiten calcular el número de dominación Grundy en grafos hipersplit y araña bien etiquetada (dado el problema resuelto en la cabeza) y en grafos block, extendiendo los resultados para árboles probados en [1].

[1] B. Bresar, T. Gologranc, M. Milanic, D. Rall, R. Rizzi. Dominating sequences in graphs. Discrete Mathematics.