Resumen de Dominación quasiperfecta e independencia en grafos. Quasi-perfect domination and independence in graphs
Sahar A. Aleid
Las propiedades de dominación han sido extensamente estudiadas dentro de la Teoría de Grafos. En la literatura se pueden encontrar muchas variantes de modelos de dominación, tales como la dominación independiente, la dominación total, la dominación romana o la dominación conexa, por mencionar solo algunos de ellos.
La dominación independiente fue introducida dentro de la Teoría de Juegos por Neumann and Margenstern, en 1944. Nosotros dedicamos nuestro trabajo a demostrar la existencia de un tipo especial de conjuntos dominantes e independientes en varias clases de grafos, además de estudiar los parámetros asociados.
Cuando se piensa en la existencia de un conjunto dominante en un grafo dado, el problema principal consiste en buscar tal conjunto con un número mínimo de vértices y en el caso de encontrar un conjunto dominante que sea independiente, el problema se vuelve más difícil. Los investigadores también han tratado de probar la existencia de tales conjuntos con propiedades adicionales, por ejemplo, conjuntos dominantes independientes tales que cada vértice fuera del conjunto tiene el mínimo número de vecinos en él. Esto ha llevado a la definición de conjunto dominante eficiente, que es aquel conjunto dominante e independiente tal que cada vértice fuera del mismo tiene exactamente un vecino en él. El estudio de estos conjuntos está íntimamente relacionado con los códigos correctores de errores.
Desafortunadamente, la existencia de conjuntos dominantes eficientes no está garantizada en todos los grafos. Una construcción menos exigente sería mantener la dominación y la independencia, pero admitir más vecinos para los vértices que no están en el conjunto dominante. Esta idea desemboca en la definición de conjunto [1,2]-independiente por Chellali y otros en 2014, que es aquel conjunto independiente de vértices S de un grafo G tal que todo vértice v∈V(G)\S tiene al menos uno y como mucho dos vecinos en S. En particular esto significa que un conjunto [1,2]-independiente es también un conjunto dominante.
Nuestro trabajo se centra en la existencia de conjuntos [1,2]-independientes para diferentes clases de grafos, tales como los árboles, las cuadrículas y las orugas. Nuestra idea surgió del hecho de que la existencia de estos conjuntos no está garantizada en todos los grafos, por lo tanto, el primer paso lógico en este estudio es dar prominencia a la existencia en vez de a la minimalidad de tales conjuntos. Sin embargo, también hemos logramos calcular el parámetro asociado, esto es, el número [1,2]-independiente, que es el mínimo cardinal de un conjunto [1,2]-independiente, para algunos de los grafos estudiados.
Los árboles tienen una estructura rica y a la vez simple, con una amplia aplicación en la Teoría de Grafos. Por lo tanto, esto fue una motivación para nosotros para comenzar nuestro estudio con esta familia de grafos. Nuestro primer resultado fue la caracterización de los grafos que admiten conjuntos [1,2]-independientes, en términos de árboles generadores, proporcionando una condición necesaria. Además, encontramos que esta condición es también suficiente para la familia de los grafos cactus. También nos fijamos en el concepto de árboles excelentes y caracterizamos a la familia de árboles tales que cada vértice pertenece a algún conjunto [1,2]-independiente. Finalmente presentamos un algoritmo para determinar si un árbol dado tiene un conjunto [1,2]-independiente. Además, este algoritmo se puede modificar fácilmente para encontrar el número [1,2]-independiente de un árbol.
Para las cuadrículas, es conocido que sólo en unos pocos casos particulares estos grafos admiten conjuntos dominantes eficientes. En ese caso, como se mencionó anteriormente, necesitamos relajar las condiciones, y así logramos nuestro segundo objetivo que es demostrar que cada cuadrícula tiene un conjunto [1,2]-independiente. También calculamos el número [1,2]-independiente para todas las cuadrículas. La razón para elegir esta clase de grafos se debe a su estructura especial, que le proporciona una construcción bien organizada en la que ninguna región del área de trabajo permanece sin representar.
Por último, para los grafos tipo oruga, probamos la existencia de conjuntos [1,2]-independientes proporcionando condiciones locales, dependiendo del grado de los vértices que pertenecen a la espina dorsal de este tipo de grafos. Además, para una familia particular de orugas, estudiamos en profundidad la relación entre conjuntos [1,2]-independientes y conjuntos dominantes independientes. Así obtenemos una cota superior para el número [1,2]-independiente, en términos del número de dominación independiente, y presentamos un teorema de realización que proporciona ejemplos de todos los valores posibles que estos dos parámetros pueden tener en dicha familia. Con ese teorema finalmente mostramos que la diferencia entre ambos parámetros puede alcanzar cualquier valor entero no negativo.
