Problema de la $\{k\}$-dominación total en nuevas subclases de grafos

ESCALANTE, MARIANA SILVINA; LOPEZ PUJATO, MARIA INES; LEONI, VALERIA ALEJANDRA

Salta

Congreso; sesión de Matemática Discreta de la XXLII Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2023

UMA

Los problemas de dominaci´on total consisten en asignar recursos (usualmente escasos) a diferentes lugares,de forma de cubrir una necesidad en la vecindad pr´oxima de ese lugar. Ejemplos de aplicaciones que puedenser modeladas por estos problemas son los problemas de ubicaci´on y/o asignaci´on de servicios: cajerosautom´aticos, c´amaras de seguridad, entre otros.En este trabajo abordamos una variante del problema de dominaci´on total que fue introducida en [4] yest´a definida de la siguiente manera: dado un grafo G con conjunto de v´ertices V y un entero no negativok (fijo), una funci´on f : V → {0, 1, . . . , k} es una funci´on {k}-dominante total de G si f (N(v)) ≥ kpara cada v´ertice v del grafo G, donde N(v) denota el subconjunto de los v´ertices adyacentes a v, yf(U) = Pv∈Uf(v) (peso de la funci´on f sobre el conjunto U) para cualquier U ⊂ V . El n´umero de{k}-dominaci´on total de G, γt{k}(G), es el peso de una funci´on {k}-dominante total de G de m´ınimo pesosobre el conjunto de v´ertices V . El problema de {k}-dominaci´on total consiste en hallar este m´ınimon´umero para un grafo G dado y un entero no negativo k. Para k = 1, este problema coincide con el dedominaci´on total en grafos, muy estudiado en la literatura espec´ıfica.Respecto a la complejidad computacional, los problemas de decisi´on asociados a estos problemas sonNP-dif´ıciles para cada k fijo ([3] y [5]). Por otra parte, se conocen instancias donde se puede resolver entiempo polinomial, ver por ejemplo [1], [2] y [5]. En [2] se presenta el valor del n´umero de {k}-dominaci´ontotal para los grafos ciclos, caminos, grafos rueda (wheels) y grafos que consisten en la 1-suma de un cicloy un camino de longitud dos (grafo pan).Siguiendo esta l´ınea de investigaci´on, analizamos la complejidad del problema de {k}-dominaci´on total enotras familias de grafos. Con el objetivo de completar este estudio en la clase de los grafos cactus (1-sumade caminos y ciclos) comenzamos estudiando los grafos obtenidos por 1-suma de un ciclo con un caminode cualquier longitud, superclase de los grafos pan. Hallamos el n´umero de {k}-dominaci´on total paraesta familia, para todo entero no negativo k. Adem´as, a partir de los resultados obtenidos y aquellos en[2], analizamos la {k}-dominaci´on total sobre los grafos oruga (caterpillar).Trabajo en conjunto con Mariana Escalante (Conicet-UNR) y Valeria Leoni (Conicet-UNR)..Referencias[1] G. Argiroffo, V. Leoni and P. Torres, Complexity of k-tuple total and total {k}-dominations for somesubclasses of bipartite graphs, Information Processing Letters 138 (2018) 75-80.[2] T. Haisheng, L. Liuyan and L. Hongyu, Total {k}-domination in special graphs, Mathematical Foundations of Computing, 1, 3 (2018).[3] J. He and H. Liang, Complexity of Total {k}-Domination and Related Problems, Lecture Notes inComputer Science 6681 (2011), 147-155.[4] N. Li and X. Hou, On the total {k}-domination number of Cartesian products of graphs, J. Comb.Optim 18 (2009) 173-178.[5] D. Pradhan, Algorithmic aspects of {k}-tuple total domination in graphs, Inform. Process. Lett. 112(21) (2012) 816–822.