Sobre los prohibidos minimales de [h,2,1], con h>2

LILIANA ALCÓN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI

Corrientes

Jornada; XXI Jornada de Jóvenes Investigadores 2013.; 2013

El grafo de intersección de una familia es un grafo cuyos vértices son los miembros de la familia y dos vértices son adyacentes si la intersección de los correspondientes miembros es no vacía. Algunas clases de grafos definidas como intersección son hereditarias, y pueden ser caracterizadas por subgrafos inducidos prohibidos minimales. Ejemplos clásicos son los grafos de intervalos y los grafos cordales.  Un grafo es de intervalos si el grafo de intersección de una familia de intervalos cerrados en la recta real o, en forma equivalente, el grafo de intersección de una familia de subcaminos de un camino. Un grafo es cordal si el grafo de intersección de una familia de subárboles en un árbol. Clases especiales de grafos son definidas poniendo restricciones en los árboles, subárboles y considerando intersección de los subárboles por vértices o por aristas, y muchas de éstas son hereditarias. Una (h,s,t)-representación de un grafo G consiste de una colección de subárboles de un árbol T, donde cada subárbol corresponde a un vértice de G, tal que (i) el grado máximo de T es a lo sumo h, (ii) cada subárbol tiene grado máximo a lo sumo s, (iii) hay una arista entre dos vértices en el grafo G si y sólo si los subárboles correspondientes tienen al menos t vértices en común en T. La clase de grafos que tiene una    (h,s,t)-representación es notada [h,s,t]. Cuando no hay restricción en el grado de T o en el grado de los subárboles escribimos h = ∞ y s = ∞, respectivamente. Notemos que [∞,∞,1] es la clase de los grafos cordales; [2,2,1] es la clase de los grafos de intervalos; [∞,2,1] es la bien conocida clase de los grafos VPT. Los grafos VPT son útiles en muchas áreas, entre las cuales cabe destacar la genética, arqueología y ecología.  La clase de grafos que admite una representación VPT en un árbol huésped con grado máximo a lo sumo h se denota [h,2,1]. Se sabe que el problema de reconocer a los grafos VPT es polinomial.  Por otro lado, el problema de decidir si un grafo cualquiera VPT pertenece a [h,2,1] es NP-completo aún cuando nos restringimos a la clase de los grafos que son VPT, Split y no tienen vértices estables dominados. Las clases [h,2,1], h>1, son cerradas por subgrafos inducidos prohibidos, de ahí que pueden ser caracterizadas por una familia de subgrafos inducidos prohibidos minimales. Tal familia se conoce  para h=2 y hay algunos resultados parciales para h=3. En este trabajo asociamos los subgrafos inducidos prohibidos minimales de [h,2,1] que son VPT con los grafos críticos. Describimos cómo obtener subgrafos inducidos prohibidos minimales a partir de los grafos críticos, más aún, mostramos que la familia de grafos obtenida usando nuestro procedimiento es exactamente la familia de subgrafos inducidos prohibidos minimales de [h,2,1] que son VPT, Split y no tienen vértices estables dominados. Además, probamos que los subgrafos inducidos prohibidos minimales de [h,2,1] que son VPT pertenecen a la clase [h+1,2,1]. Finalmente, conjeturamos que todos los prohibidos minimales de [h,2,1], con h>2, que son VPT pueden ser obtenidos de un grafo (h+1)-crítico.