En nuestro próximo encuentro, el martes 14 de octubre a las 15 hs, nos reuniremos, como en cada seminario, en la sala 2119 del Pabellón 0+Infinito.

Este será el segundo encuentro presentado por Lucía Busolini, quien dará una charla titulada “Grafos distancia-hereditarios balanceados”.  

Resumen:
Una matriz de 0 y 1's es balanceada (Berge, 1972) si no contiene como submatriz una matriz cuadrada de orden impar con exactamente dos 1's por fila y por columna.
Un grafo G es balanceado si su matriz de incidencia cliques maximales vs. vértices es balanceada. Bonomo, Durán, Lin y Szwarcfiter (2006) probaron que un grafo es balanceado si y sólo si no contiene soles impares generalizados como subgrafos inducidos. Sin embargo, esta caracterización no es una caracterización por subgrafos inducidos prohibidos minimales ya que algunos soles impares generalizados contienen otros soles impares generalizados como subgrafos inducidos propios. No se conoce todavía una caracterización por subgrafos inducidos prohibidos minimales de la clase de grafos balanceados en general, aunque se lograron encontrar algunas caracterizaciones parciales.
Un grafo G se dice distancia-hereditario si es conexo y la distancia entre cualquier par de vértices es la misma en G que en cualquier subgrafo inducido conexo H de G. Además, existen varias definiciones equivalentes de esta clase de grafos, varias de las cuales mencionamos el martes pasado en el seminario, entre la que podemos destacar la definición recursiva de Chang, Hsieh y Chen (1997).
En esta charla voy recordar algunos trabajos previos que nos fueron útiles para lograr caracterizar los grafos distancia-hereditarios balanceados, que ya los mencionamos el martes pasado, expondré una caracterización estructural de esta clase de grafos y un algoritmo lineal de reconocimiento.

Aquellas personas interesadas en participar frecuentemente en este seminario, son invitadas a unirse a nuestro grupo de Telegram: https://t.me/+RkVxwjjIdiE1Yjkx y visitar la página del seminario: https://web.dm.uba.ar/index.php/investigacion/seminarios/seminario-grafos.