Asteroidal quadruples in non rooted path graphs

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path gra...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Gutiérrez, Marisa, Leveque, Benjamín, Tondato, Silvia B.
Formato: Articulo
Lenguaje:Inglés
Publicado: 2015
Materias:
Matemática
Asteroidal quadruples
Clique trees
Rooted path graphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/85929
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-85929
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
Asteroidal quadruples
Clique trees
Rooted path graphs
spellingShingle Matemática
Asteroidal quadruples
Clique trees
Rooted path graphs
Gutiérrez, Marisa
Leveque, Benjamín
Tondato, Silvia B.
Asteroidal quadruples in non rooted path graphs
topic_facet Matemática
Asteroidal quadruples
Clique trees
Rooted path graphs
description A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed path graphs that are non rooted path graphs. We prove that such graphs always contain an asteroidal quadruple.
format Articulo
Articulo
author Gutiérrez, Marisa
Leveque, Benjamín
Tondato, Silvia B.
author_facet Gutiérrez, Marisa
Leveque, Benjamín
Tondato, Silvia B.
author_sort Gutiérrez, Marisa
title Asteroidal quadruples in non rooted path graphs
title_short Asteroidal quadruples in non rooted path graphs
title_full Asteroidal quadruples in non rooted path graphs
title_fullStr Asteroidal quadruples in non rooted path graphs
title_full_unstemmed Asteroidal quadruples in non rooted path graphs
title_sort asteroidal quadruples in non rooted path graphs
publishDate 2015
url http://sedici.unlp.edu.ar/handle/10915/85929
work_keys_str_mv AT gutierrezmarisa asteroidalquadruplesinnonrootedpathgraphs
AT levequebenjamin asteroidalquadruplesinnonrootedpathgraphs
AT tondatosilviab asteroidalquadruplesinnonrootedpathgraphs
bdutipo_str Repositorios
_version_ 1764820489129164803

Ejemplares similares