Título: Problema de dominación eterna para grafos de intervalos
Director: Francisco Soulignac
Jurados: Brian Curcio y Verónica Moyano (UNGS)

RESUMEN
Consideremos un juego por turnos sobre un grafo G = (V, E) jugado por un atacante y un defensor.  Inicialmente, el defensor ubica guardias sobre los vértices de G.  En cada turno, el atacante elige un vértice v para atacar y el defensor mueve algunos guardias, a vértices adyacentes a sus posiciones actuales, a fin de ubicar al menos un guardia en v.  Los problemas de dominación eterna consisten en determinar la mínima cantidad de guardias con las que se puede defender eternamente a G.  En particular, \gamma_{n,1}(G) y \gamma_{n,1}(G) denotan la cantidad mínima de guardias necesarios cuando no y sí se pueden posicionar guardias simultáneamente sobre el mismo vértice, respectivamente.  En esta tesis demostramos que si G es un grafo de intervalos, entonces \gamma_{n,1}(G) = \gamma_{n,n}(G) = \theta_c(G), donde \theta_c(G) es el número de cubrimiento clique-conexo de G.  Más aún, damos un algoritmo lineal para computar un conjunto dominante eterno de mínima cardinalidad.