Árboles generadores en grafos aleatorios II.

Abstract: En el último seminario vimos que el grafo aleatorio binomial Gn,p es universal para la familia de árboles con muchas hojas apartadas. Siguiendo con el estudio del artículo “Spanning trees in random graphs” de Montgomery, en este seminario, veremos las técnicas utilizadas para demostrar que Gn,p es universal para árboles con muchos caminos de determinado largo. En especial, se presentará el método de rotación-extensión de Pósa para encontrar caminos largos en grafos.

Posted on Oct 17, 2022 in Seminario de Grafos, Seminars