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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/139126 |
| Aporte de: |
| Sumario: | 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. |
|---|