On Models of Directed Path Graphs Non Rooted Directed Path Graphs

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted directed path graph is the intersection graph of a family of directed subpaths of a rooted tree. Clearly, rooted directed path graphs are directed path graphs. Several characterizations are...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Gutiérrez, Marisa, Tondato, Silvia Beatriz
Formato: Articulo Preprint
Lenguaje:Inglés
Publicado: 2016
Materias:
Matemática
Asteroidal quadruples
Clique trees
Rooted directed path graphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/99524
https://ri.conicet.gov.ar/11336/54360
https://link.springer.com/article/10.1007/s00373-015-1600-z
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-99524
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 directed path graphs
spellingShingle Matemática
Asteroidal quadruples
Clique trees
Rooted directed path graphs
Gutiérrez, Marisa
Tondato, Silvia Beatriz
On Models of Directed Path Graphs Non Rooted Directed Path Graphs
topic_facet Matemática
Asteroidal quadruples
Clique trees
Rooted directed path graphs
description A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted directed path graph is the intersection graph of a family of directed subpaths of a rooted tree. Clearly, rooted directed 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 directed path graphs. With the purpose of proving knowledge in this direction, we show in this paper properties of directed path models that can not be rooted for chordal graphs with any leafage and with leafage four. Therefore, we prove that for leafage four directed path graphs minimally non rooted directed path graphs have a unique asteroidal quadruple, and can be characterized by the presence of certain type of asteroidal quadruples.
format Articulo
Preprint
author Gutiérrez, Marisa
Tondato, Silvia Beatriz
author_facet Gutiérrez, Marisa
Tondato, Silvia Beatriz
author_sort Gutiérrez, Marisa
title On Models of Directed Path Graphs Non Rooted Directed Path Graphs
title_short On Models of Directed Path Graphs Non Rooted Directed Path Graphs
title_full On Models of Directed Path Graphs Non Rooted Directed Path Graphs
title_fullStr On Models of Directed Path Graphs Non Rooted Directed Path Graphs
title_full_unstemmed On Models of Directed Path Graphs Non Rooted Directed Path Graphs
title_sort on models of directed path graphs non rooted directed path graphs
publishDate 2016
url http://sedici.unlp.edu.ar/handle/10915/99524
https://ri.conicet.gov.ar/11336/54360
https://link.springer.com/article/10.1007/s00373-015-1600-z
work_keys_str_mv AT gutierrezmarisa onmodelsofdirectedpathgraphsnonrooteddirectedpathgraphs
AT tondatosilviabeatriz onmodelsofdirectedpathgraphsnonrooteddirectedpathgraphs
bdutipo_str Repositorios
_version_ 1764820493429374978

Ejemplares similares