Sesión Matemática DiscretaHacia una caracterización de grafos italianos y grafos sicilianos
Alberto José Ferrari
Universidad Nacional de Rosario, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un subconjunto $D$ de vértices de un grafo $G$ es un conjunto dominante en $G$ si todo vértice fuera de $D$ es adyacente a al menos un vértice de $D$. El tamaño mínimo de un conjunto dominante en un grafo $G$ es llamado el número de dominación de $G$ y denotado por $\gamma(G)$ (Berge, 1958).
Numerosos y diversos problemas de la vida real pueden ser formulados como problemas de dominación en grafos, por ejemplo asignar recursos (usualmente escasos) a diferentes lugares de forma de cubrir una necesidad en ese lugar y su vecindad próxima. Muchas variantes de la dominación usual han sido y siguen siendo estudiadas en la literatura. En este trabajo nos enfocamos en dos variantes, la $\{2\}$-dominación y la dominación italiana.
Dado un grafo $G$ con conjunto de vértices $V$, una función de dominación italiana $f : V \rightarrow \{0, 1, 2\}$ tiene la propiedad de que para cada vértice $v\in V$ con $f(v) =0$, o bien existe un vértice $u$ adyacente a $v$ con $f(u) = 2$, o al menos dos vértices $x,\; y$ adyacentes a $v$ con $f(x)=f(y)=1$. El peso de una función de dominación italiana es el valor $f(V) = \sum_{v\in V} f(v)$. El mínimo peso de una función de dominación italiana en $G$ es llamado el número de dominación italiano de $G$ y denotado por $\gamma_{I}(G)$ [1]. La dominación italiana está fuertemente relacionada con la $\{2\}$-dominación, introducida por Hedetniemi et al. en 1991, en la que, además de la propiedad mencionada para la dominación italiana, también se pide que para cada vértice $v \in V$ con $f(v)=1$, exista al menos un vértice $u$ adyacente a $v$ con $f(u) \neq 0$. El mínimo peso de una función $\{2\}$-dominante en $G$ es llamado el número de $\{2\}$-dominación de $G$ y denotado por $\gamma_{\{2\}}(G)$.
Al comparar la dominación usual y la dominación italiana, en [1] los autores presentan la siguiente desigualdad: $\gamma(G) \leq \gamma_I(G) \leq 2\gamma(G)$. En [5] se define un grafo italiano $G$ como aquel tal que $\gamma_I(G) = 2\gamma(G)$. En [4] se presenta una caracterización de los grafos árboles italianos. Sin embargo no se conocía una caracterización general de los grafos italianos.
Claramente, si $G$ es un grafo italiano, conociendo el valor exacto y/o un algoritmo eficiente que encuentra $\gamma(G)$, se conocerá el valor exacto de $\gamma_I(G)$ y recíprocamente. De aquí la importancia de tener una caracterización de ellos o de algunas otras subclases. En este trabajo introducimos la definición de grafo I2a como aquel para el cual el rango de alguna función de dominación italiana de peso mínimo es $\{0,2\}$. Probamos que un grafo $G$ es I2a si y sólo si $G$ es italiano.
Por otro lado, en [6] los autores presentan la siguiente desigualdad: $\gamma_I(G) \leq \gamma_{\{2\}}(G)$ para todo grafo $G$. No es difícil probar que $\gamma_{\{2\}}(G)\leq 2 \gamma(G)$. En base a esto, nosotros introducimos una superclase de los grafos italianos: $G$ es un grafo siciliano si $\gamma_{I}(G)= \gamma_{\{2\}}(G)$.
En un trabajo reciente, el número $\gamma_{\{2\}}(G)$ fue obtenido para una clase relevante de grafos, la de los grafos web $G$ [2]. Nos propusimos entonces estudiar el número de dominación italiana para esta clase de grafos y en [3] mostramos cómo obtuvimos el valor de $\gamma_{I}(G)$ para todo grafo web $G$. Exhibimos una subfamilia infinita de grafos web que son sicilianos pero no italianos.
Con el objetivo de avanzar hacia una caracterización de los grafos sicilianos, en este trabajo nos enfocamos en los grafos complementos de los grafos bipartitos (co-bipartitos), obteniendo los valores de $\gamma_{I}(G)$ y $\gamma_{\{2\}}(G)$ para todo grafo co-bipartito $G$. Presentamos también una subfamilia infinita de grafos co-bipartitos que son sicilianos pero no italianos. Probamos que todo grafo siciliano no italiano y para el cual no existe una función de dominación italiana con rango $\{0,1\}$, tiene número de dominación italiana por lo menos 4. Encontramos condiciones necesarias para que dicha cota se alcance por igualdad.
Trabajo en conjunto con: Valeria Leoni (Conicet - Universidad Nacional de Rosario) y María Inés Lopez Pujato (Universidad Nacional de Rosario).
Referencias
[1] Chellali, M., Haynes, T. W., Hedetniemi, S. T., McRae, A. A., Roman {2}-domination, Discrete Appl. Math., 204, (2016) 22-28.
[2] Cheng, Y. J., Fu, H. L., Liu, C. A., The integer {k}-domination number of circulant graphs, Discrete Math. Algorithms Appl., 12, 4 (2020) 2050055, 1-9.
[3] Ferrari, A. J., Leoni, V., Lopez Pujato, M. I., Dominación italiana, 2-dominación y {2}-dominación en grafos, XVII Congreso Dr. Antonio Monteiro, (2023).
[4] Henning, M. A., Klostermeyer, W. F., Italian domination in trees, Discrete Appl. Math., 217, (2017) 557-564.
[5] Klostermeyer, W. F., MacGillivray, G., Roman, italian, and 2-domination, J. Combin. Math. Combin. Comput, 108, (2019) 125-146.
[6] Wang, C. X., Yang Y., Wang, H. J., Xu S. J., Roman {k}-domination in trees and complexity results for some classes of graphs, J. Comb. Optim., 42, (2021) 174-186.