Helly EPT graphs on bounded degree trees : Characterization and recognition

The edge-intersection graph of a family of paths on a host tree is called an <i>EPT</i> graph. When the tree has maximum degree h, we say that the graph is [<i>h</i>, 2, 2]. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly [<i>h...

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: 2017
Materias:
Matemática
Intersection graphs
EPT graphs
Tolerance graphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/102919
https://www.sciencedirect.com/science/article/abs/pii/S0012365X17302571?via%3Dihub
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-102919
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Intersection graphs
EPT graphs
Tolerance graphs
spellingShingle Matemática
Intersection graphs
EPT graphs
Tolerance graphs
Alcón, Liliana Graciela
Gutiérrez, Marisa
Mazzoleni, María Pía
Helly EPT graphs on bounded degree trees : Characterization and recognition
topic_facet Matemática
Intersection graphs
EPT graphs
Tolerance graphs
description The edge-intersection graph of a family of paths on a host tree is called an <i>EPT</i> graph. When the tree has maximum degree h, we say that the graph is [<i>h</i>, 2, 2]. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly [<i>h</i>, 2, 2]. In this paper, we present a family of <i>EPT</i> graphs called gates which are forbidden induced subgraphs for [<i>h</i>, 2, 2] graphs. Using these we characterize by forbidden induced subgraphs the Helly [<i>h</i>, 2, 2] graphs. As a byproduct we prove that in getting a Helly <i>EPT</i> -representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly [<i>h</i>, 2, 2] graphs based on their decomposition by maximal clique separators.
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 Helly EPT graphs on bounded degree trees : Characterization and recognition
title_short Helly EPT graphs on bounded degree trees : Characterization and recognition
title_full Helly EPT graphs on bounded degree trees : Characterization and recognition
title_fullStr Helly EPT graphs on bounded degree trees : Characterization and recognition
title_full_unstemmed Helly EPT graphs on bounded degree trees : Characterization and recognition
title_sort helly ept graphs on bounded degree trees : characterization and recognition
publishDate 2017
url http://sedici.unlp.edu.ar/handle/10915/102919
https://www.sciencedirect.com/science/article/abs/pii/S0012365X17302571?via%3Dihub
work_keys_str_mv AT alconlilianagraciela hellyeptgraphsonboundeddegreetreescharacterizationandrecognition
AT gutierrezmarisa hellyeptgraphsonboundeddegreetreescharacterizationandrecognition
AT mazzolenimariapia hellyeptgraphsonboundeddegreetreescharacterizationandrecognition
bdutipo_str Repositorios
_version_ 1764820440829657089

Ejemplares similares