On k-tree Containment Graphs of Paths in a Tree

A k-tree is either a complete graph on k vertices or a graph that contains a vertex whose neighborhood induces a complete graph on k vertices and whose removal results in a k-tree. If the comparability graph of a poset P is a k-tree, we say that P is a k-tree poset. In the present work, we study and...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gudiño, Noemí Amalia, Gutiérrez, Marisa
Formato: Articulo
Lenguaje:Inglés
Publicado: 2020
Materias:
Matemática
Containment models
Comparability graphs
k-trees
CPT posets
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/139126
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-139126
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
Containment models
Comparability graphs
k-trees
CPT posets
spellingShingle Matemática
Containment models
Comparability graphs
k-trees
CPT posets
Alcón, Liliana Graciela
Gudiño, Noemí Amalia
Gutiérrez, Marisa
On k-tree Containment Graphs of Paths in a Tree
topic_facet Matemática
Containment models
Comparability graphs
k-trees
CPT posets
description A k-tree is either a complete graph on k vertices or a graph that contains a vertex whose neighborhood induces a complete graph on k vertices and whose removal results in a k-tree. If the comparability graph of a poset P is a k-tree, we say that P is a k-tree poset. In the present work, we study and characterize by forbidden subposets the k-tree posets that admit a containment model mapping vertices into paths of a tree (CPT k-tree posets). Furthermore, we characterize the dually-CPT and strong-CPT k-tree posets and their comparability graphs. The characterizations lead to efficient recognition algorithms for the respective classes.
format Articulo
Articulo
author Alcón, Liliana Graciela
Gudiño, Noemí Amalia
Gutiérrez, Marisa
author_facet Alcón, Liliana Graciela
Gudiño, Noemí Amalia
Gutiérrez, Marisa
author_sort Alcón, Liliana Graciela
title On k-tree Containment Graphs of Paths in a Tree
title_short On k-tree Containment Graphs of Paths in a Tree
title_full On k-tree Containment Graphs of Paths in a Tree
title_fullStr On k-tree Containment Graphs of Paths in a Tree
title_full_unstemmed On k-tree Containment Graphs of Paths in a Tree
title_sort on k-tree containment graphs of paths in a tree
publishDate 2020
url http://sedici.unlp.edu.ar/handle/10915/139126
work_keys_str_mv AT alconlilianagraciela onktreecontainmentgraphsofpathsinatree
AT gudinonoemiamalia onktreecontainmentgraphsofpathsinatree
AT gutierrezmarisa onktreecontainmentgraphsofpathsinatree
bdutipo_str Repositorios
_version_ 1764820457096216576

Ejemplares similares