Árboles generadores en digrafos densos.

Resumen: En el año 2001 se encontró una condición del grado mínimo para grafos con n vértices que aseguraba la contención de todo árbol generador de grado máximo acotado por cn/log(n). En este seminario se muestra que el mismo resultado, cambiando grado mínimo por semigrado mínimo, se tiene para árboles orientados y digrafos. Este fue demostrado en el presente año por Kathapurkar y Montgomery, quienes utilizaron un método distinto al clásico lema de Regularidad.

Posted on Sep 27, 2021 in Seminario de Grafos, Seminars