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
id I19-R120-10915-164530
record_format dspace
spelling I19-R120-10915-1645302024-04-08T20:47:49Z http://sedici.unlp.edu.ar/handle/10915/164530 A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs Alcón, Liliana Graciela Gutiérrez, Marisa Mazzoleni, María Pía 2010 2024-04-08T13:09:01Z en Ciencias Exactas Matemática intersection graphs EPT graphs 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 do not satisfy the previous condition, as a consequence we present a nite family of minimal forbidden subgraphs for the EPT class. Facultad de Ciencias Exactas Departamento de Matemática Articulo Articulo http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf 111-120
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Exactas
Matemática
intersection graphs
EPT graphs
forbidden subgraphs
spellingShingle Ciencias Exactas
Matemática
intersection graphs
EPT graphs
forbidden subgraphs
Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs
topic_facet Ciencias Exactas
Matemática
intersection graphs
EPT graphs
forbidden subgraphs
description 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.
format Articulo
Articulo
author Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
author_facet Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
author_sort Alcón, Liliana Graciela
title A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs
title_short A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs
title_full A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs
title_fullStr A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs
title_full_unstemmed A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs
title_sort necessary condition for ept graphs and a new family of minimal forbidden subgraphs
publishDate 2010
url http://sedici.unlp.edu.ar/handle/10915/164530
work_keys_str_mv AT alconlilianagraciela anecessaryconditionforeptgraphsandanewfamilyofminimalforbiddensubgraphs
AT gutierrezmarisa anecessaryconditionforeptgraphsandanewfamilyofminimalforbiddensubgraphs
AT mazzolenimariapia anecessaryconditionforeptgraphsandanewfamilyofminimalforbiddensubgraphs
AT alconlilianagraciela necessaryconditionforeptgraphsandanewfamilyofminimalforbiddensubgraphs
AT gutierrezmarisa necessaryconditionforeptgraphsandanewfamilyofminimalforbiddensubgraphs
AT mazzolenimariapia necessaryconditionforeptgraphsandanewfamilyofminimalforbiddensubgraphs
_version_ 1807222374337085440

Ejemplares similares