Resumen

Dado un grafo G=(V,E) y dos aristas e,f en E, decimos que e domina a f si e=f o si e y f tienen un extremo en común.
Decimos que un subconjunto P de E es un conjunto perfecto de aristas dominantes (PED por sus siglas en inglés) si toda arista de E menos P está 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 o DIM por sus siglas en inglés) si toda arista de E está dominada por exactamente una arista de M.
En esta charla hablaremos sobre dos resultados: la complejidad del problema PED en grafos sin DIM, y un algoritmo polinomial para hallar un PED de cardinalidad mínima en grafos sin P6 inducidos.