De dominación y otras perversiones... en la Teoría de Gráficas

En 1848, en el ámbito ajedrecista, se planteó la pregunta de si es posible acomodar 8 reinas en un tablero de ajedrez sin que se ataquen unas a otras, es fácil ver que 9 reinas ya no pueden ser colocadas sin que se ataquen entre sí. En 1850 se obtiene las primeras soluciones y en ese mismo año otra pregunta surge. ¿Cuál es el número de reinas que hay que colocar en un tablero para que toda casilla tenga una reina o sea alcanzada por una en un movimiento y que con menos de ese número ya no sea posible? Esta pregunta fue respondida por Jaenisch en 1862, quien demostró que 5 es el mínimo número de reinas que se necesitan para dominar a todo el tablero. Es así como nace el estudio de los conjuntos dominantes en gráficas.

  En esta plática definiremos el número de dominación de una gráfica, conoceremos tal número para algunas familias de gráficas y daremos unas cotas para otras. También añadiremos otras características a los conjuntos además de ser dominantes y cambiaremos un poco la manera de cómo van a dominar, definiendo así nuevos tipos de dominación. Y tal vez, dependiendo de nuestra creatividad, hasta podemos inventar nuevos tipos de dominación.