Artículo
On Models of Directed Path Graphs Non Rooted Directed Path Graphs
Fecha de publicación:
03/2016
Editorial:
Springer Tokyo
Revista:
Graphs And Combinatorics
ISSN:
0911-0119
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
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.
Palabras clave:
Asteroidal Quadruples
,
Clique Trees
,
Rooted Directed Path 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
Gutierrez, Marisa; Tondato, Silvia Beatriz; On Models of Directed Path Graphs Non Rooted Directed Path Graphs; Springer Tokyo; Graphs And Combinatorics; 32; 2; 3-2016; 663-684
Compartir
Altmétricas