Determinando qué conjuntos de árboles pueden ser los árboles clique de un grafo cordal

PABLO DE CARIA; MARISA GUTIERREZ

San Miguel de Tucumán

Congreso; LXI Reunión de comunicaciones científicas de la UMA; 2011

Unión Matemática Argentina

Los grafos cordales son definidos como aquellos grafos cuyos ciclos de longitud mayor o igual que cuatro poseen una cuerda. Una condición necesaria y suficiente para que un grafo G sea cordal es la existencia de un árbol clique T, el cual está definido de la siguiente manera: sus vértices son los cliques de G, es decir, los conjuntos maximales de vértices adyacentes de a pares, y se cumple que, para cada vértice v de G, el conjunto de cliques que tienen a v como elemento induce un subárbol de T.Encontrar todos los árboles clique de un grafo cordal dado no es simple, ya que el número total de árboles clique de un grafo cordal puede ser exponencial. En esta exposición se estudiará un problema que va en la dirección inversa: dado un conjunto V y una familia T de árboles, todos con V como conjunto de vértices, determinar si existe un grafo cordal tal que todos sus árboles clique son los de T . El procedimiento hallado para responder a la cuestión es polinomial con respecto a |V| y |T| y también permite, en caso afirmativo, construir un grafo cordal cuyo familia de árboles clique es T. Además, todos los grafos que son posibles soluciones para el problema serán caracterizados.Otra clase de grafos afín a la de los grafos cordales es la de los dualmente cordales. Estos pueden ser definidos como los grafos que poseen un árbol generador tal que todo clique del grafo induce un subárbol. En base a esto, se planteará un problema similar al ya enunciado y ambos serán comparados.