A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs

An undirected graph G is called an EPT graph if it is the edge intersection graph of a family of paths in a tree. In this paper we de ne the concept of satellite of a clique and we give a necessary condition to be an EPT graph based on satellites of cliques. We characterize the minimal graphs which...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gutiérrez, Marisa, Mazzoleni, María Pía
Formato: Articulo
Lenguaje:Inglés
Publicado: 2010
Materias:
Ciencias Exactas
Matemática
intersection graphs
EPT graphs
forbidden subgraphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/164530
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
Descripción
Sumario:An undirected graph G is called an EPT graph if it is the edge intersection graph of a family of paths in a tree. In this paper we de ne the concept of satellite of a clique and we give a necessary condition to be an EPT graph based on satellites of cliques. We characterize the minimal graphs which do not satisfy the previous condition, as a consequence we present a nite family of minimal forbidden subgraphs for the EPT class.

Ejemplares similares