Los grafos estrella extendida: reconocimiento y propiedades estructurales

PABLO DE CARIA; SILVIA TONDATO; MARISA GUTIERREZ

Bahía Blanca

Congreso; LXV Reunión anual de Comunicaciones Científicas de la UMA; 2016

Unión Matemática Argentina

Los grafos cordales, aquellos cuyos ciclos de longitud mayor o igual que cuatro poseen una cuerda (arista entre vértices no consecutivos del ciclo), pueden ser caracterizados a través del árbol clique. Dado un grafo G, diremos que un árbol T es un árbol clique de G si el conjunto de vértices de T consiste en los cliques de G y, para todo vértice v de V(G), el conjunto C_v de cliques de G que contienen a v induce un subárbol en T. Un grafo es cordal si y sólo si posee un árbol clique.Es habitual definir subclases de los grafos cordales a través de la condición de que el grafo posea un tipo especial de árbol clique. Estas condiciones se pueden referir a la estructura del árbol en sí o a la estructura de los subárboles inducidos por los conjuntos C_v.Recientemente se han definido los grafos estrella extendida (extended star en inglés) como aquellos grafos cordales que poseen un árbol clique tal que a lo sumo un vértice de él posea grado mayor que dos. Como consecuencia, se desprende inmediatamente que los grafos de intervalos forman una subclase de grafos estrella extendida. Ambas clases tienen en común que se pueden caracterizar a través de la ausencia de ciertos tipos de triplas asteroidales.En esta presentación, nos centraremos en el reconocimiento de los grafos estrella extendida. Para ello, introduciremos el concepto de clique central. Un clique de un grafo estrella extendida se dice central cuando es un vértice de grado máximo de un árbol clique del grafo con las características que definen la clase. Veremos cómo se puede determinar si un clique dado es central y desarrollaremos un método de reconocimiento de grafos estrella extendida basado en la identificación de potenciales cliques centrales. Para ello, utilizaremos técnicas de descomposición del grafo, las cuales a su vez nos ayudarán para obtener más propiedades estructurales de los grafos estrella extendida.