Prohibidos minimales de [h,2,1]

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

Rosario

Congreso; LXII Reunión Anual de Comunicaciones Científicas. 2013; 2013

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) todo subárbol tiene grado máximo a lo sumo s, (iii) existe 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 se denota [h,s,t]. Un grafo no dirigido G es VPT si es el grafo vértice intersección de una familia de caminos en un árbol.En cite{gravril,nuevo}, se muestra que el problema de reconocer a los grafos VPT es polinomial.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]. Recientemente, en cite{pia}, generalizando un resultado dado en cite{B4}, hemos probado que el problema de decidir si un grafo VPT pertenece a [h,2,1] es NP-completo.Las clases [h,2,1], con $hgeq 2$, son cerradas por subgrafos inducidos prohibidos, de ahí que cada una de ellas puede ser caracterizada por una familia de subgrafos inducidos prohibidosminimales. Tal familia es conocida para h=2 cite{B8} y hay algunos resultados parciales para h=3 cite{hugo}. En este trabajo, asociamos los subgrafos inducidos prohibidos minimales para [h,2,1] que son VPT con los grafos críticos. Describimos cómo obtener subgrafos inducidos prohibidosminimales 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 para [h,2,1] que son VPT. Esta familia junto con la familia de subgrafos inducidos prohibidos minimales para VPT cite{B9,B11}, es la familia de subgrafos inducidos prohibidos minimales para [h,2,1], con $hgeq 3$.