Sesión Matemática Discreta y Teoría de Juegos\(\{k\}\)-dominación total en orugas: propiedades estructurales y resultados exactos.
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.
En este trabajo nos enfocamos en el estudio del problema de la \(\{k\}\)-dominación total (\(T\{k\}DP\)) en familias de grafos con una cierta estructura, como los grafos oruga (caterpillar). Un grafo oruga es un árbol con la propiedad adicional de que, al eliminar todas sus hojas, se obtiene un camino, llamado camino central de la oruga. Un vértice soporte es un vértice del camino central adyacente a una hoja.
Dado un grafo \(G\) y un entero no negativo \(k\), una función se llama \(\{k\}\)-dominante total en \(G\) si está definida sobre sus vértices y asume valores en \(\{0,\dots,k\}\) de manera que su peso en la vecindad abierta de cada vértice sea al menos \(k\). El \(T\{k\}DP\) busca entonces hallar una función \(\{k\}\)-dominante total de peso mínimo [4]. Dicho peso mínimo es el número de k-dominación total en \(G\).
Se sabe el peso mínimo de una función \(\{k\}\)-dominante total para varias clases de grafos: ciclos, caminos, rueda (wheels) y tipo sartenes (pans) [2]. Sin embargo, para cada valor de \(k\), este problema es NP-difícil para familias generales de grafos [3]. En un trabajo previo [1] se estudió el \(T\{k\}DP\) para el caso particular de grafos oruga en los que las vecindades abiertas de los vértices soporte son mutuamente disjuntas.
En este trabajo, extendemos el estudio realizado anteriormente a cualquier grafo oruga. Para ello, se logró reducir en esta familia el \(T\{k\}DP\) al problema de dominación total clásico que corresponde a \(k=1\). La herramienta central de este análisis es la introducción de una representación \((T,R)\), una aplicación biyectiva que abstrae la estructura de la oruga en vectores enteros basados en la distribución de los vértices soporte y las longitudes de los segmentos del camino central. Utilizando esta representación, obtenemos una expresión exacta para el número de \(\{k\}\)-dominación total de cualquier grafo oruga, para todo entero \(k\).
Trabajo en conjunto con: Mariana S. Escalante (Universidad Nacional de Rosario, CONICET, Argentina) y Paola Tolomei (Universidad Nacional de Rosario, CONICET, Argentina).
Referencias
[1] Escalante, Mariana, M. Inés Lopez Pujato and Paola Tolomei. On total $\{k\}$-domination in caterpillar graphs. Procedia Computer Science 273 ( 2025) 429-436.
[2] Haisheng, Tan, Liu Liuyan, and Liang Hongyu. Total $\{k\}$-Domination in Special Graphs. Mathematical Foundations of Computing 1 (3) (2018) 255--263.
[3] He, Jing, and Hongyu Liang. Complexity of total $\{k\}$-domination and related problems. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management 6681 (2011) 147--155.
[4] Li, Ning, and Xinmin Hou. On the total $\{k\}$-domination number of Cartesian products of graphs. Journal of Combinatorial Optimization volume 18 (2009) 173--178.