Sesión Matemática DiscretaDominación italiana en grafos con "pocos" caminos inducidos de 4 vértices
Lara Fernández
FCEIA (UNR) y CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dado un grafo $G$ con conjunto de vértices $V$, decimos que $f:V\rightarrow \{0,1,2\}$ es una función de dominación italiana (o función de $\{2\}$-dominación romana) en $G$ si en cada $v\in V$ tal que $f(v)=0$, la suma de los valores asignados por $f$ a los vértices adyacentes a $v$ es al menos 2. Es decir que si $f(v)=0$, $v$ debe ser adyacente en $G$ a al menos un vértice $u$ con $f(u)=2$ o a dos vértices distintos $x,y$ tales que $f(x)=f(y)=1$. El peso de $f$ es la suma de $f(v)$ sobre $V$. El número de dominación italiana de $G$, $\gamma_{I}(G)$, es el menor peso entre todas las funciones de dominación italiana en $G$. La dominación italiana es una de las variantes de la dominación clásica (Berge, 1958) definida en los últimos años [2].
El problema de decisión asociado a este nuevo concepto, el problema de la función de dominación italiana (R2DP), 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, R2DP es NP-difícil [2, 4], aunque se conocen algunas clases de grafos donde el problema se puede resolver eficientemente (entre ellas, en un trabajo previo mostramos un algoritmo eficiente que resuelve R2DP para cualquier grafo caterpillar [4]).
Un grafo es $F$-free si no tiene como subgrafo inducido a ningún miembro de $F$. Recientemente se ha demostrado que R2DP es NP-difícil para grafos $(2K_2,C_4,C_5)$-free (o grafos split) [3]. Claramente, como consecuencia, R2DP es NP-difícil aún para grafos $(2K_2, C_4)$-free. Por otro lado, en [1] se prueba que el problema puede resolverse en tiempo polinomial para grafos que son $(2K_2, C_4)$-free y además $P_4$-free (cografos); estos son los grafos threshold. Sin embargo, en [5] se había demostrado que R2DP puede resolverse en tiempo polinomial en todo cografo.
Resulta prometedor continuar el estudio de la complejidad computacional de R2DP en otras superclases de grafos threshold, y más aún, de cografos. Nos enfocamos entonces en aquellas familias de grafos definidas por la presencia de un número acotado de caminos con 4 vértices (o $P_4$s).
En el presente trabajo comenzamos estudiando cómo se comporta el número de dominación italiana ante diferentes operaciones entre grafos y, haciendo uso de la descomposición modular conocida de los cografos, presentamos una nueva demostración de la polinomialidad de R2DP en esta clase. Este enfoque nos permite probar la polinomialidad del problema en grafos $P_4$-sparse y en grafos $P_4$-tidy. Mostramos por último los avances obtenidos sobre grafos partner-limited, con el objeto de extender lo más posible la polinomialidad de R2DP, o en su defecto, determinar una frontera en esta línea.
Trabajo en conjunto con: Valeria Leoni (FCEIA (UNR) y CONICET, Argentina).
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(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, pp.22-28, 2016.
[3] Chen H. and Lu C. Roman $\{2\}$-Domination Problem in Graphs, Discussiones Mathematicae Graph Theory, 42(2), pp.641-660, 2022.
[4] Fernández, L. and Leoni V., New complexity results on Roman $\{2\}$-domination, RAIRO-Oper. Res., Forthcoming article, 2023. https://doi.org/10.1051/ro/2023049
[5] W. Klostermeyer and G. Mac Gillivray, Roman, italian and 2-domination, Journal of Combinatorial Mathematics and Combinatorial Computing, 108, pp.125-146, 2019.