Dominación en gráficas coloreadas

El número de dominación Γ(G)</em> de una gráfica G es el tamaño de un conjunto D más pequeño de vértices de G tal que cada vértice fuera de D tiene al menos un vecino en D, es decir, D es un conjunto dominante de G. Además, hay varios resultados que tratan el problema de la dominación en gráficas coloreadas . En ellos, la definición es demasiado restrictiva para algunas aplicaciones y sus autores consideran que una coloración de dominación de una gráfica G es una coloración de G tal que cada vértice de G domina al menos una clase de colores, y cada clase de color es dominada por al menos un vértice.

Sin embargo, es natural pensar en un orden en cualquier relación de dominación. De esta manera, introducimos un concepto natural de dominación en el contexto de grafos coloreados.

Dado un grafo G(V,E), una coloración de G es una asignación c: V → {0,1,2...} tal que c(vᵢ)≠c(vⱼ) si vᵢ y vⱼ son vértices adyacentes. Si la coloración utiliza exactamente k colores, se le llama una k–coloración, y, como es bien sabido, el número cromático χ(G) de una gráfica G es el valor mínimo de k.

Entonces, cualquier coloración c de G(V,E) proporciona un ordenamiento (parcial) natural de V, y así el par (G, c) puede considerarse como una digráfica acíclica tal que cada arista comienza desde su vértice con el color más alto.

Finalmente, dado un grafo G con una coloración c, decimos que D⊆V es un conjunto dominante de color ascendente c del par (G, c) si: (1) para cualquier vértice v que no esté en D existe un vértice adyacente d \in D tal que c(v) < c(d); (2) D no contiene ningún vértice de color 0. Así, c y D establecen una relación dominante–sumisa en G, en la que los vértices v y d son sumisos y dominantes, respectivamente.

Las definiciones anteriores nos permiten definir dos objetivos de optimización diferentes. De esta manera, siguiendo la tradición, podemos minimizar el tamaño del conjunto dominante y así el cardinal más pequeño de un conjunto dominante de color ascendente para el par (G,c) se llama el número de dominación de color ascendente de c de (G, c) y se denota por Γ_{uc}(G,c).

Por otro lado, dado que la coloración proporciona de manera natural un peso a los vértices del grafo (y a subconjuntos de los vértices, sumando los pesos individuales), el peso mínimo de un conjunto dominante de color ascendente para el par (G, c) se llama el peso de dominación de color ascendente de (G, c) y se denota por ω_{uc}(G,c).

Platicaremos sobre algunos resultados sobre estos parámetros a lo largo de la charla.