Artículo
Recent results on containment graphs of paths in a tree
Fecha de publicación:
08/2018
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
In this paper, motivated by the questions posed by Spinrad in Spinrad (2003) and Golumbic and Trenk (2004), we investigate those posets that admit a containment model mapping vertices into paths of a tree and their comparability graphs, named CPT posets and CPT graphs, respectively. We present a necessary condition to be CPT and prove it is not sufficient. We provide further examples of CPT posets P whose dual Pd is non CPT. Thus, we introduce the notion of dually-CPT and strong-CPT posets. We demonstrate that, unlike what happens with posets admitting a containment model using interval of the line, the dimension and the interval dimension of CPT posets is unbounded. On the other hand, we find that the dimension of a CPT poset is at most the number of leaves of the tree used in the containment model. We give a characterization of CPT (also dually-CPT and strong-CPT) split posets by a family of forbidden subposets. We prove that every tree is strong-CPT.
Palabras clave:
Comparability Graphs
,
Geometric Containment Models
,
Posets
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; Gudiño, Noemí Amalia; Gutierrez, Marisa; Recent results on containment graphs of paths in a tree; Elsevier Science; Discrete Applied Mathematics; 245; 8-2018; 139-147
Compartir
Altmétricas