Sesión Matemática DiscretaCaracterización de grafos distancia-hereditario balanceados
Lucía Busolini
Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Matemática & CONICET-Universidad de Buenos Aires, Instituto de Cálculo (IC), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Una matriz $A \in \{0, 1\}^{n\times m}$ es balanceada [2] 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 [3] si su matriz de incidencia cliques maximales vs. vértices es balanceada. Bonomo, Durán, Lin y Szwarcfiter [4] 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, entre las cuales podemos mencionar la caracterización dentro de la clase de grafos sin diamantes [1], sin paw [5], cobipartitos, grafos de línea de multigrafos y complementos de grafos de línea de multigrafos [6].
Un grafo $G$ se dice distancia-hereditario si es conexo y la distancia entre cualquier par de vértices $x,y \in V(G)$ es la misma en $G$ que en cualquier subgrafo inducido conexo $H$ de $G$. Se sabe que los grafos distancia-hereditarios son perfectos [8] y clique-perfectos [9]. Además, existen varias definiciones equivalentes de esta clase de grafos, entre la que podemos destacar la definición recursiva de Chang, Hsieh y Chen [7].
En esta charla voy a mencionar algunos trabajos previos que fueron fundamentales para lograr caracterizar los grafos distancia-hereditarios balanceados y expondré también un algoritmo lineal de reconocimiento para esta clase de grafos.
Trabajo en conjunto con: Guillermo Durán (Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Matemática & CONICET-Universidad de Buenos Aires, Instituto de Cálculo) y Martín D. Safe (Departamento de Matemática, Universidad Nacional del Sur (UNS) & INMABB, Universidad Nacional del Sur (UNS)-CONICET, Bahía Blanca, Argentina).
Referencias
[1] N. Apollonio y A. Galluccio. “Minimally unbalanced diamond-free graphs and Dyck-paths”. SIAM J. Discrete Math. 29.4 (2015), p´ags. 1837-1863.
[2] C. Berge. “Balanced matrices”. Math. Program. 2.1 (1972), págs. 19-31.
[3] C. Berge y V. Chvátal, eds. Topics on perfect graphs. Vol. 88. North-Holland Mathematics Studies. Annals of Discrete Mathematics, 21. North-Holland, Amsterdam, 1984, págs. xiv+369.
[4] F. Bonomo, G. Durán, M. C. Lin y J. L. Szwarcfiter. “On balanced graphs”. Math. Program. 105.2-3, Ser. B (2006), págs. 233-250.
[5] F. Bonomo, G. Durán, M. D. Safe y A. K. Wagler. “Clique-perfectness and balancedness of some graph classes”. Int. J. Comput. Math. 91.10 (2014), págs. 2118-2141.
[6] F. Bonomo, G. Durán, M. D. Safe y A. K. Wagler. “On minimal forbidden subgraph characteri- zations of balanced graphs”. Discrete Appl. Math. 161.13-14 (2013), págs. 1925-1942.
[7] M.-S. Chang, S.-y. Hsieh y G.-H. Chen. “Dynamic programming on distance-hereditary graphs”. Algorithms and computation (Singapore, 1997). Vol. 1350. Lecture Notes in Comput. Sci. Springer, Berlin, 1997, págs. 344-353.
[8] E. Howorka. “A characterization of distance-hereditary graphs”. Quart. J. Math. Oxford Ser. (2) 28.112 (1977), págs. 417-420.
[9] C.-M. Lee y M.-S. Chang. “Distance-hereditary graphs are clique-perfect”. Discrete Appl. Math. 154.3 (2006), págs. 525-536.