Resumen de Dominación en grafos cilíndricos
José Juan Carreño Carreño
Este trabajo está dedicado al estudio de algunas propiedades de dominación en grafos cilíndricos, es decir, grafos que se construyen como el producto cartesiano de un ciclo y un camino de cualquier orden. Es bien conocido que las propiedades de dominación no tienen una traslación inmediata de los factores al producto cartesiano, por lo que se hace necesario el estudio individualizado de casos concretos, como son los cilindros, a los que hemos enfocado nuestro trabajo.
Por una parte, abordamos el concepto de dominación eficiente, centrándonos en los conjuntos [1,2]-independientes. Puesto que se sabe que los cilindros carecen, en su mayoría, de conjuntos dominantes eficientes, el interés del estudio de conjuntos [1,2]-independientes radica en que constituyen una alternativa, que demostraremos que es factible, en esta familia de grafos.
Por otra parte, estudiamos la dominación clásica, mediante el cálculo del parámetro asociado, esto es, el número de dominación. Dicho parámetro no está calculado en cilindros de tamaño arbitrario, pudiéndose encontrar en la literatura cotas superiores e inferiores no ajustadas y valores exactos para casos particulares, donde o bien el ciclo o bien el camino son de orden pequeño (menor que 30). Nosotros vamos a obtener una cota inferior general, que mejora las conocidas hasta ahora, y que proporciona el valor exacto de γ(Pm□Cn), cuando m ≥ 20 y 30 ≤ n ≡ 0 (mod 5).
Comenzamos con una breve introducción histórica de la Teoría de Grafos y enunciamos las definiciones de los conceptos básicos de grafos que vamos a utilizar. Nos centramos en las propiedades de dominación y en la operación producto cartesiano de grafos.
A continuación, caracterizamos completamente los grafos cilíndricos Cm□Pn que poseen conjuntos [1,2]-independientes. Demostramos que todos los cilindros, salvo el caso particular del producto cartesiano de un ciclo con cinco vértices y un camino con dos vértices, poseen tales conjuntos. Destacamos que la demostración constructiva que presentamos permite obtener los valores exactos del parámetro asociado, el número [1,2]-independiente, para los casos Cm□P2 (m ≠ 5) y C3□Pn, así como cotas superiores, no ajustadas en general, para el resto de los casos.
También calculamos los valores exactos del número [1,2]-independiente para los cilindros Cm□Pn, en los casos 4 ≤ m ≤15. Para esto utilizamos una modificación del algoritmo para calcular el número de dominación del producto cartesiano de dos caminos, que ya es conocido. En una primera instancia realizamos las modificaciones imprescindibles para cambiar el tipo de grafos al que se aplica (el original es para el producto cartesiano de dos caminos y nosotros lo aplicamos al producto de un ciclo y un camino) y la propiedad de dominación con la que se trabaja (dominación clásica en el original y dominación [1,2]-independiente en nuestro caso). Sin embargo, estos cambios son útiles solo para los casos m=4,5, siendo necesarias las modificaciones adicionales, que presentamos detalladamente, para poder abordar el resto de los casos.
Finalmente, proporcionamos una cota inferior general para el número de dominación (clásica) de un cilindro arbitrario. También demostramos que dicha cota es ajustada cuando el ciclo tiene orden un múltiplo de cinco. Este es la primera vez que se calcula el valor exacto del número de dominación de una familia de cilindros donde ni el orden del ciclo ni el orden del camino están acotados
