Sesión Matemática Discreta y Teoría de JuegosReconocimiento de grafos \(\{2\}\)-romanos
Lara Fernández
FCEIA y FCEYE - UNR, 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, \ldots , k\}\) es una función \(\{k\}\)-romana dominante en \(G\) si \(\sum_{u\in N(v)} f(u) \geq k\) para cada vértice \(v\in V\) con \(f (v) = 0\). El peso de \(f\), es la suma de \(f(v)\) sobre \(V\). Denotamos por \(\gamma_{\{Rk\}}(G)\), al menor peso entre todas las funciones \(\{k\}\)-romana dominantes en \(G\).
La dominación \(\{k\}\)-romana es una de las variantes de la dominación clásica (Berge, 1958) más recientes, definida por Wang et al. en 2021 [2]. Todo grafo \(G\) verifica la desigualdad \(\gamma_{\{Rk\}}(G) \leq k\gamma(G)\) donde \(\gamma(G)\) es el número de dominación clásico. En particular, en [2] presentan una caracterización mediante ciertas operaciones para los árboles \(T\) que verifican \(\gamma_{\{Rk\}}(T) = k\gamma(T)\), que definen como árboles \(\{k\}\)-romanos.
Nuestro estudio se centra en los grafos \(\{k\}\)-romanos, es decir, aquellos grafos \(G\) que verifican la igualdad \(\gamma_{\{Rk\}}(G) = k\gamma(G)\), lo cual extiende el concepto de árboles \(\{k\}\)-romanos dado por Wang et al. a grafos en general, y se enfoca en el estudio la complejidad computacional de su problema de reconocimiento asociado.
En efecto, en [1] introdujimos los grafos \(\{k\}\)-romanos e iniciamos el estudio del problema de reconocimiento asociado, probando que para \(k\geq 3\), ese problema es NP-difícil incluso para grafos split. Sin embargo, no nos fue posible extender el resultado al caso de los grafos \(\{2\}\)-romanos, para el cual solo mostramos que el problema de reconocimiento es polinomial en la clase de grafos middle.
En el presente trabajo, nos centramos en la complejidad computacional del reconocimiento de los grafos \(\{2\}\)-romanos. Analizamos un enfoque diferente al planteado en [1] y analizamos la posibilidad de extender este nuevo resultado a cualquier valor de \(k\geq 2\).
Trabajo en conjunto con: K. Bešter Štorgel (FIS, Universidad de Novo Mesto - FAMNIT, Universidad de Primorska, Eslovenia), N. Chiarelli (FAMNIT- IAM, Universidad de Primorska, Koper, Eslovenia), J. P. Gollin (FAMNIT, Universidad de Primorska, Koper, Eslovenia), C. Hilaire (FAMNIT, Universidad de Primorska, Koper, Eslovenia), V. Leoni (FCEIA, Universidad Nacional de Rosario - CONICET) y M. Milanič (FAMNIT- IAM, Universidad de Primorska, Koper, Eslovenia).
Referencias
[1] K. Bešter Štorgel, N. Chiarelli, L. Fernández, J. P. Gollin, C. Hilaire, V. Leoni, and M. Milanič. On {k}-Roman graphs. Procedia Computer Science, 273:325–332, 2025.
[2] C.-X. Wang, Y. Yang, H.-J. Wang, and S.-J. Xu. Roman {k}-domination in trees and complexity results for some classes of graphs. Journal of Combinatorial Optimization, 42:174–186, 2021.