Reconociendo familias de árboles clique de grafos cordales y sus subfamilias

PABLO DE CARIA; MARISA GUTIERREZ

Rosario

Congreso; LXII Reunión anual de Comunicaciones Científicas de la UMA; 2013

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 C_v de cliques que tienen a v como elemento induce un subárbol de T.Encontrar un árbol clique de un grafo cordal G dado es simple desde el punto de vista algorítmico, pero el número total de árboles clique de G puede ser exponencial. En un trabajo previo, se consideró el siguiente problema: dada una familia T de árboles con conjunto V de vértices, determinar si existe un grafo cordal cuya familia de árboles clique es T. Allí se muestra que el problema puede ser resuelto en tiempo polinomial con respecto a |T| y a |V|.Algunos grafos cordales poseen tipos especiales de árboles clique. Un UV-árbol clique T de G es un árbol clique tal que C_v induce un camino en T para todo vértice v de G. Decimos además que T es un DV-árbol clique si sus aristas pueden ser orientadas de modo que C_v induce un camino dirigido en T para todo vértice v de G.En este trabajo se considerarán versiones más complejas del problema descrito en el segundo párrafo. No sólo se proporcionará una familia T de árboles, sino también una subfamilia T', pidiéndose la condición adicional de que los árboles de T' sean los UV o DV árboles clique del grafo que se busca.