Cayley Trees and Increasing 1,2-Trees: Let's Twist!
The Electronic Journal of Combinatorics · 05.06.2026 · 33 (2)
DOI: 10.37236/13980 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 05.06.2026. Verfasst von Julien Courtiel und 2 weiteren Autor:innen.
Abstract (Originalsprache)
An increasing 1,2-tree is a labeled graph formed by starting with a vertex and then repeatedly attaching a leaf to a vertex or a triangle to an edge, the labeling of the vertices corresponding to the order in which the vertices are added. Equivalently, increasing 1,2-trees are connected chordal graphs of treewidth at most 2 labeled with a reversed perfect elimination ordering. We prove that this family is equinumerous with Cayley trees, which are unconstrained labeled trees. In particular, the number of triangles in an increasing 1,2-tree corresponds to the number of twists. A twist (also called improper edge) is an edge whose endpoint closer to vertex 1 has a greater label than some vertex in the subtree rooted at the other endpoint of the edge. We provide three proofs of this result, the first being based on similar recursive decompositions, the second on the resolution of generating functions, and the third describing a bijection. Finally, we propose efficient random generators for these two combinatorial families.
Zitieren
APA
Courtiel, J., Dien, M., & Dorbec, P. (2026). Cayley Trees and Increasing 1,2-Trees: Let's Twist!. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/13980
Vancouver
Courtiel J, Dien M, Dorbec P. Cayley Trees and Increasing 1,2-Trees: Let's Twist!. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/13980
BibTeX
@article{Courtiel2026,
author = {Courtiel, Julien and Dien, Matthieu and Dorbec, Paul},
title = {Cayley Trees and Increasing 1,2-Trees: Let's Twist!},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {2},
doi = {10.37236/13980}
}
EUVIMED