Artículo
Helly EPT graphs on bounded degree trees: Characterization and recognition
Fecha de publicación:
12/2017
Editorial:
Elsevier Science
Revista:
Discrete Mathematics
ISSN:
0012-365X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
The edge-intersection graph of a family of paths on a host tree is called an EPT graph. When the tree has maximum degree h, we say that the graph is [h,2,2]. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly [h,2,2]. In this paper, we present a family of EPT graphs called gates which are forbidden induced subgraphs for [h,2,2] graphs. Using these we characterize by forbidden induced subgraphs the Helly [h,2,2] graphs. As a byproduct we prove that in getting a Helly EPT-representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly [h,2,2] graphs based on their decomposition by maximal clique separators.
Palabras clave:
EPT GRAPHS
,
INTERSECTION GRAPHS
,
TOLERANCE GRAPHS
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
Alcón, Liliana Graciela; Gutierrez, Marisa; Mazzoleni, María Pía; Helly EPT graphs on bounded degree trees: Characterization and recognition; Elsevier Science; Discrete Mathematics; 340; 12; 12-2017; 2798-2806
Compartir
Altmétricas