Grafos distancia-hereditarios balanceados

Título:  Grafos distancia-hereditarios balanceados

Fecha: Martes 14 de octubre a las 15 hs, sala 2119 del Pabellón 0+Infinito.

Expone: Lucía Busolini, Instituto de Cálculo, FCEN, UBA

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.