Recognizing clique graphs of directed edge path graphs

Directed edge path graphs are the intersection graphs of directed paths in a directed tree, viewed as sets of edges. They were studied by Monma and Wei (J. Comb. Theory B 41 (1986) 141-181) who also gave a polynomial time recognition algorithm. In this work, we show that the clique graphs of these g...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Gutiérrez, Marisa, Meidanis, João
Formato: Articulo
Lenguaje:Inglés
Publicado: 2003
Materias:
Ciencias Exactas
Clique graphs
Intersection graphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/83487
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-83487
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Exactas
Clique graphs
Intersection graphs
spellingShingle Ciencias Exactas
Clique graphs
Intersection graphs
Gutiérrez, Marisa
Meidanis, João
Recognizing clique graphs of directed edge path graphs
topic_facet Ciencias Exactas
Clique graphs
Intersection graphs
description Directed edge path graphs are the intersection graphs of directed paths in a directed tree, viewed as sets of edges. They were studied by Monma and Wei (J. Comb. Theory B 41 (1986) 141-181) who also gave a polynomial time recognition algorithm. In this work, we show that the clique graphs of these graphs are exactly the two sections of the same kind of path families, and give a polynomial time recognition algorithm for them.
format Articulo
Articulo
author Gutiérrez, Marisa
Meidanis, João
author_facet Gutiérrez, Marisa
Meidanis, João
author_sort Gutiérrez, Marisa
title Recognizing clique graphs of directed edge path graphs
title_short Recognizing clique graphs of directed edge path graphs
title_full Recognizing clique graphs of directed edge path graphs
title_fullStr Recognizing clique graphs of directed edge path graphs
title_full_unstemmed Recognizing clique graphs of directed edge path graphs
title_sort recognizing clique graphs of directed edge path graphs
publishDate 2003
url http://sedici.unlp.edu.ar/handle/10915/83487
work_keys_str_mv AT gutierrezmarisa recognizingcliquegraphsofdirectededgepathgraphs
AT meidanisjoao recognizingcliquegraphsofdirectededgepathgraphs
bdutipo_str Repositorios
_version_ 1764820488666742785

Ejemplares similares