On k -tree Containment Graphs of Paths in a Tree
- PDF / 888,158 Bytes
- 16 Pages / 439.642 x 666.49 pts Page_size
- 53 Downloads / 265 Views
On k -tree Containment Graphs of Paths in a Tree ´ 1,2 · Noem´ı Gudino ˜ 1,2 Liliana Alcon
· Marisa Gutierrez1,2
Received: 18 January 2019 / Accepted: 20 July 2020 / © Springer Nature B.V. 2020
Abstract 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 ktree. 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 (CP T k-tree posets). Furthermore, we characterize the dually-CP T and strong-CP T k-tree posets and their comparability graphs. The characterizations lead to efficient recognition algorithms for the respective classes. Keywords Containment models · Comparability graphs · k-trees · CP T posets
1 Introduction and Definitions Different classes of posets have been defined by imposing geometric restrictions to the sets used in their containment models [2, 4, 5, 8, 16]. Posets admitting a containment model using intervals of a line, which are called CI posets and are known to be the posets with dimension at most 2, are exactly the posets whose comparability graphs belong to the well understood class of permutation graphs [3]. In [1, 2], we have initiated the study of those posets that admit a containment model mapping vertices into paths of a tree, which are called CP T posets and clearly constitute a superclass of CI posets. We have found remarkable differences between CI and CP T posets. First, the dimension of CI posets is bounded above by 2, but the dimension of CP T posets is unbounded, this means that for every positive integer d there exists some CP T poset with dimension greater than d. Second, any Noem´ı Gudi˜no
[email protected] Liliana Alc´on [email protected] Marisa Gutierrez [email protected] 1
CMaLP, FCE-UNLP, La Plata, Argentina
2
CONICET, Buenos Aires, Argentina
Order
CI poset admits a CI model using non trivial paths, however, there exist CP T posets that require the use of trivial paths in any CP T model. And third, the fact of being a CI poset is a comparability invariant, but the fact of being CP T is not. Figure 1 illustrates the previous observations, the poset Nd is CP T . In any CP T representation of Nd the vertex labelled b has to be represented by a trivial path. The dual poset N is non CP T [2]. Determining classes of posets in which being CP T is an invariant of comparability and understanding the structure behind it is a challenging problem. In Section 4, we solve this problem within a subclass of CP T posets. As opposed to the previous differences, both classes are hereditary, meaning that any subposet of a CI (resp. CP T ) poset is also CI (resp. CP T ). Consequently, they admit a characterization by a family of minimal forbidden subposets. It is well known that the forbidden structures for being CI are the 3-irreducible posets, i.e. the m
Data Loading...
