On k-tree Containment Graphs of Paths in a Tree
Autor: | Noemí Gudiño, Marisa Gutierrez, Liliana Alcón |
---|---|
Rok vydání: | 2020 |
Předmět: |
Containment (computer programming)
Matemática Mathematics::Combinatorics Algebra and Number Theory Containment models CPT posets k-trees Comparability Complete graph Comparability graph Tree (graph theory) Vertex (geometry) Combinatorics Computational Theory and Mathematics Geometry and Topology K-tree Partially ordered set Comparability graphs Mathematics |
Zdroj: | SEDICI (UNLP) Universidad Nacional de La Plata instacron:UNLP |
ISSN: | 1572-9273 0167-8094 |
DOI: | 10.1007/s11083-020-09536-1 |
Popis: | 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. Centro de Investigación de Matemática |
Databáze: | OpenAIRE |
Externí odkaz: |