Intersección de cliques y las aristas y caminos en los árboles clique de los grafos cordales

PABLO DE CARIA

Buenos Aires

Seminario; Sexto Seminario de la Red Latinoamericana, "Optimización Discreta y Grafos: Teoría, Algoritmos y Aplicaciones"; 2013

Universidad de Buenos Aires

Los grafos cordales, aquellos sin ciclos inducidos de longitud mayor a tres, pueden caracterizarse por la existencia de un árbol clique. Un árbol clique T de un grafo cordal G posee a los cliques de G como vértices y, para todo vértice v de G, el conjunto de cliques que tienen a v como elemento induce un subárbol en T. De esta definición se infiere que todo árbol clique de G es un árbol generador del grafo clique de G, por lo que sus aristas tienen como extremos a cliques de G con intersección no vacía. Sin embargo, no es necesariamente cierto que cualquier par de cliques de G con intersección no vacía aparezca como arista de algún árbol clique de G. En esta exposición se estudiarán los grafos cordales en los que sí toda arista del grafo clique es arista de algún árbol clique. Más aun, también se considerarán a los grafos cordales en los que todo camino del grafo clique es camino de algún árbol clique. Se mostrará que estos grafos pueden caracterizarse a través de subgrafos prohibidos minimales y, en base a ello, se obtendrán propiedades adicionales acerca de los árboles clique de estos grafos.