Familias de árboles inducidos en un grafo

PABLO DE CARIA

La Plata

Congreso; LXVII Reunión Anual de Comunicaciones Científicas de la UMA; 2018

Unión Matemática Argentina

Las familias de conjuntos que pueden representarse como subárboles de un árbol han recibido bastante atención en el ámbito de la matemática discreta al poseer varias aplicaciones. La clase de grafos de intersección de subárboles de un árbol resulta ser igual a la de los grafos cordales, que también poseen alta relevancia. Este hecho permite caracterizar a los grafos cordales a través del árbol clique. Un árbol T se dice que es un árbol clique del grafo G si V(T) es igual al conjunto de cliques maximales de G y, para cada vértice v de G, el conjunto C_v de cliques maximales de G que contienen a v induce un subárbol en T. Un grafo es cordal sí y sólo si posee un árbol clique.Esta presentación tratará sobre generalizaciones del árbol clique, utilizando grafos que no necesariamente son árboles. Esto se ha logrado exitosamente en ciertas superclases de los grafos cordales, como los grafos libres de ruedas, manteniendo varias propiedades estructurales.Nos concentraremos en el caso más general de todos. Consideraremos un grafo G y nos preguntaremos si existe un grafo H cuyos vértices son los cliques maximales de G, de manera que, para todo v en V(G), C_v induce un árbol en H. Veremos en este caso que la mayoría de las propiedades del árbol clique se pierden. Por ejemplo, la clase de grafos G que admiten un grafo H como fuera descrito anteriormente no es hereditaria.Finalmente, dada una familia F de conjuntos, veremos que es NP-completo decidir si existe un grafo H tal que F puede representarse como familia de árboles inducidos en H. Esto implicará que determinar si un grafo G posee las propiedades del párrafo anterior también es NP-completo.