Una condición necesaria para ser un grafo EPT y una nueva familia de subgrafos prohibidos minimales.

MARÍA PÍA MAZZOLENI

Ciudad del Este

Jornada; XIX Jornada de Jóvenes Investigadores 2011; 2011

Asociación de Universidades Grupo Montevideo

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.           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. Un grafo no dirigido G es llamado un grafo EPT si es el grafo arista intersección de una familia de caminos en un árbol. Los grafos EPT son usados en aplicaciones de redes, donde el problema de planificación de llamadas no dirigidas en una red que es un árbol es equivalente al problema de colorear un grafo EPT. El problema de reconocer a los grafos EPT es NP-completo. En este trabajo definimos el concepto de satélite de un clique, y damos una condición necesaria para ser un EPT grafo basada en los satélites de los cliques. Caracterizamos a los grafos minimales que no satisfacen esta condición y, como una consecuencia, presentamos una familia finita de subgrafos minimales prohibidos para la clase EPT.