Un estudio conjunto de grafos cordales y dualmente cordales

Abstract

Los grafos cordales fueron definidos originalmente como aquellos grafos para los cuales todo ciclo de longitud mayor o igual que cuatro posee una cuerda. Los gafos cordales han sido estudiados exhaustivamente debido a que se les han encontrado muchas aplicaciones, especialmente en el campo de la biología. Como resultado de esas investigaciones, surgieron varias caracterizaciones nuevas de los grafos cordales que involucran diversos conceptos, como los de separador minimal de vértices, vértice simplicial y árbol clique. Un clique de un grafo G es un conjunto maximal de vértices adyacentes de a pares. El grafo clique de G tiene a los cliques de G como vértices, siendo dos de ellos adyacentes si y sólo si tienen intersección no vacía. Un grafo es dualmente cordal si es el grafo clique de algún grafo cordal. Históricamente hablando, los grafos dualmente cordales aparecieron hace más de veinte años en varias investigaciones independientes bajo las más diversas denominaciones, como grafos HT, tree clique graphs y árboles expandidos. En cada una de estas investigaciones, los grafos dualmente cordales eran definidos de maneras distintas y fueron necesarios algunos años más hasta que se descubriera que todas las definiciones eran equivalentes. Por esto, podemos afirmar que, al igual que los grafos cordales, los grafos dualmente cordales poseen varias caracterizaciones. Los resultados que aparecen en este trabajo son numerosos, pero pueden ser clasificados en función de dos objetivos. En primer lugar, se buscó encontrar nuevas caracterizaciones de los grafos dualmente cordales que resultaran extensiones de las ya conocidas. Esto se ve en el Capítulo 3 y, en menor medida, en el Capítulo 4. En segundo lugar, dado que varias de las caracterizaciones de los grafos cordales y dualmente cordales son afines, se aprovechan las similaridades para realizar un estudio conjunto de ambas clases en función de esas caracterizaciones. Este es el caso, en mayor o menor medida, de los Capítulos 2, 4 y 5.