Dominación italiana en grafos caterpillar

LARA FERNANDEZ; VALERIA LEONI

Neuquén

Congreso; Reunión Anual de la Unión Matemática Argentina; 2022

Universidad Nacional del Comahue

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. [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, 3, pp.1081-1086, 2020. [2] Chellali M., T. W Haynes, S. T, Hedetniemi and A.A. McRae, Roman {2}-domination, Discrete Appl. Math., 204, 22-28, 2016.  [3] Henning M. and W. Klostermeyer, emph {Italian domination in trees}, Discrete Appl. Math. 217 (2017) 557-564.