UMA 2022
Dado un grafo $G$ con conjunto de vértices $V$, decimos que $f=(V_0,V_1, V_2)$ es una función de dominación italiana (o función de $\{2\}$-dominación romana) en $G$ si $\{V_0,V_1, V_2\}$ es una partición de $V$ de tal modo que cada vértice de $V_0$ es adyacente en $G$ a al menos dos vértices de $V_1$ o a uno de $V_2$. El peso de $f$, $w(f)$, es la suma de $f(v)$ sobre $V$. Denotamos por $\gamma_{I}(G)$ al menor peso entre todas las funciones italianas en $G$ y lo denominamos número de dominación italiana de $G$. Esta es una de las variantes de la dominación clásica (Berge, 1958) definida más recientemente [2].
El problema de decisión asociado a este nuevo concepto, el problema de la función de dominación italiana, consiste en decidir si existe en un grafo dado $G$ una función italiana de peso $\gamma_{I}(G)$. Desde el punto de vista de la complejidad computacional de problemas de decisión u optimización, este problema, como lo es el de dominación usual, es NP-difícil [2]. Resultados muy recientes muestran nuevas clases de grafos donde el mismo se mantiene NP-difícil [1].
Por otra parte, se conocen cotas para el número $\gamma_{I}(G)$ de un grafo $G$ general, como así también algoritmos exactos para hallar $\gamma_{I}(G)$ cuando $G$ es un camino o $G$ es un ciclo [2]. Además, el estudio de la dominación italiana sobre los grafos árboles fue iniciado en [3], pero no desde el punto de vista de la complejidad computacional, sino siguiendo la línea de estudio que brindan las cotas halladas en [2], mostrando caracterizaciones de aquellos árboles para los cuales algunas de esas cotas se verifican por igualdad.
En el presente trabajo abordamos el estudio de este nuevo problema en una subclase propia de los grafos árboles, la de los grafos caterpillar. $G$ es un grafo caterpillar si es conexo y consiste de un camino principal junto con vértices de grado uno adyacentes a algún vértice del camino principal. En particular, aplicamos resultados generales mostrados en [2] al estudio de la dominación italiana en grafos caterpillar.
Trabajo en conjunto con: Valeria Leoni (Universidad Nacional de Rosario y CONICET; valeoni@fceia.unr.edu.ar).
Referencias
[1] Chakradhar P, S. Venkata and R. Palagiri, Complexity of Roman {2}-domination and the double Roman domination in graphs, Akce Intenational Journal of Graphs and Combinatorics, 17 (2020), 3, 1081-1086.
[2] Chellali M., T. W Haynes, S. T, Hedetniemi and A.A. McRae, Roman {2}-domination, Discrete Appl. Math., 204 (2016), 22-28.
[3] Henning M. and W. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017) 557-564.