Sesión Matemática DiscretaProblema de la $\{k\}$-dominación total en nuevas subclases de grafos.
María Inés Lopez Pujato
Universidad Nacional de Rosario (FCEIA), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los problemas de dominación total consisten en asignar recursos (usualmente escasos) a diferentes lugares, de forma de cubrir una necesidad en la vecindad próxima de ese lugar. Ejemplos de aplicaciones que pueden ser modeladas por estos problemas son los problemas de ubicación y/o asignación de servicios: cajeros automáticos, cámaras de seguridad, entre otros.
En este trabajo abordamos una variante del problema de dominación total que fue introducida en $[4]$ y está definida de la siguiente manera: dado un grafo $G$ con conjunto de vértices $V$ y un entero no negativo $k$ (fijo), una función $f:V\rightarrow \{0,1,\dots,k\}$ es una función $\{k\}$-dominante total de $G$ si $f\left(N(v)\right)\geq k$ para cada vértice $v$ del grafo $G$, donde $N(v)$ denota el subconjunto de los vértices adyacentes a $v$, y $f(U) = \sum_{v\in U} f(v)$ (peso de la función $f$ sobre el conjunto $U$) para cualquier $U\subset V$. El número de $\{k\}$-dominación total de $G$, $\gamma_{\{k\}}^{t}(G)$, es el peso de una función $\{k\}$-dominante total de $G$ de mínimo peso sobre el conjunto de vértices $V$. El problema de $\{k\}$-dominación total consiste en hallar este mínimo número para un grafo $G$ dado y un entero no negativo $k$. Para $k = 1$, este problema coincide con el de dominación total en grafos, muy estudiado en la literatura específica.
Respecto a la complejidad computacional, los problemas de decisión asociados a estos problemas son NP-difíciles para cada $k$ fijo ($[3]$ y $[5]$). Por otra parte, se conocen instancias donde se puede resolver en tiempo polinomial, ver por ejemplo $[1]$, $[2]$ y $[5]$. En $[2]$ se presenta el valor del número de $\{k\}$-dominación total para los grafos ciclos, caminos, grafos rueda (wheels) y grafos que consisten en la 1-suma de un ciclo y un camino de longitud dos (grafo pan).
Siguiendo esta línea de investigación, analizamos la complejidad del problema de $\{k\}$-dominación total en otras familias de grafos. Con el objetivo de completar este estudio en la clase de los grafos cactus (1-suma de caminos y ciclos) comenzamos estudiando los grafos obtenidos por 1-suma de un ciclo con un camino de cualquier longitud, superclase de los grafos pan. Hallamos el número de $\{k\}$-dominación total para esta familia, para todo entero no negativo ${k}$. Además, a partir de los resultados obtenidos y aquellos en [2], analizamos la $\{k\}$-dominación 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 some subclasses 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 in Computer 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.