Los grafos básicamente cordales hereditarios y sus caracterizaciones

PABLO DE CARIA

Córdoba

Congreso; IV Congreso Latinoamericano de Matemáticos; 2012

Universidad Nacional de Córdoba

Las clases de los grafos cordales y de sus grafos clique, los grafos dualmente cordales, pueden ser caracterizadas a través de los árboles clique y los árboles compatibles, respectivamente. Los primeros tienen a los cliques del grafo como vértices y, para todo vértice del grafo, el conjunto de cliques que contienen a ese vértice induce un subárbol. Los segundos son árboles generadores del grafo y todo clique de éste induce un subárbol.El problema de determinar si, dado un grafo cordal G, los árboles clique de G son exactamente los árboles compatibles de su grafo clique ha sido recientemente estudiado. Si G satisface la propiedad aquí mencionada, se dice que es básicamente cordal. En el presente trabajo, se considerará la clase de los grafos básicamente cordales hereditarios, es decir, los grafos tales que ellos y todos sus subgrafos inducidos son básicamente cordales. Se encontrará la familia de grafos prohibidos minimales de los grafos básicamente cordales hereditarios y esto permitirá caracterizarlos de varias maneras, usando para ello propiedades de los separadores minimales y de intersección de cliques.Finalmente, se hallará una condición necesaria y suficiente para que, dado G un grafo dualmente cordal, G sea el grafo clique de un grafo básicamente cordal hereditario.