Sesión Matemática DiscretaEl problema del conjunto perfecto de aristas dominantes en grafos sin emparejamientos dominantes inducidos y grafos sin $P_6$ inducidos
Camilo Vera
Instituto de Cálculo, FCEN, UBA, 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 = (V, E)$ y dos aristas $e,f\in E$, decimos que $e$ domina a $f$ si ambas comparten un extremo o bien si $e = f$. Un subconjunto $P$ de $E$ es un conjunto perfecto de aristas dominantes (PED por sus siglas en inglés) si toda arista de $E \setminus P$ es dominada por exactamente una arista de $P$. Por otro lado, decimos que un subconjunto $M$ de $E$ es un conjunto eficiente de aristas dominantes (EED por sus siglas en inglés) si toda arista de $E$ está dominada por exactamente una arista de $M$. Claramente, todo EED es un emparejamiento dominante inducido (DIM por sus siglas en inglés) y recíprocamente, todo DIM es un EED. No todo grafo tiene un DIM. En [2] se demostró que determinar la existencia de un DIM es un problema NP-completo. Notar que un DIM es un PED de cardinalidad mínima (ver [1]).
En este trabajo demostramos que encontrar un PED de tamaño a lo sumo $k$ en un grafo conexo que no contiene un DIM es NP-completo. Además se presenta un algoritmo de tiempo polinomial para encontrar un PED de cardinalidad mínima en grafos sin $P_6$ como subgrafo inducido. Este resultado se basa en una caracterización presentada en [3] para grafos sin $P_6$ como subgrafo inducido y extiende un resultado análogo para grafos sin $P_5$ como subgrafo inducido demostrado en [4].
Trabajo en conjunto con: Luciano N. Grippo (Universidad Nacional de General Sarmiento, Argentina) y Min C. Lin (Universidad de Buenos Aires, Argentina).
Referencias
[1] C. L. Lu, M. T. Ko, C. Y. Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Applied Mathematics 119 (2002)
[2] D. L. Grinstead, P. J. Slater, N. A. Sherwani, N. D. Holmes, Efficient edge domination problems in graphs, Inform. Process. Lett. 48 (5) (1993)
[3] Pim van’t Hof, D. Paulusma, A new characterization of $P_6$-free graphs, Discrete Applied Mathematics 158 (2010)
[4] M. C. Lin, V. Lozin, V. A. Moyano, J. L. Szwarcfiter, Perfect edge domination: hard and solvable cases, Ann. Oper. Res. 264:287-305 (2018)