A combinatorial link between labelled graphs and increasingly labelled Schröder trees
Abstract
In this paper we study a model of Schröder trees whose labelling is increasing along the branches. Such tree family is useful in
the context of phylogenetic. The tree nodes are of arbitrary arity (i.e. out-degree) and the node labels can be repeated throughout different
branches of the tree. Once a formal construction of the trees is formalized, we then turn to the enumeration of the trees inspired by a renormalisation due to Stanley on acyclic orientations of graphs. We thus exhibit
links between our tree model and labelled graphs and prove a one-to-one correspondence between a subclass of our trees and labelled graphs.
As a by-product we obtain a new natural combinatorial interpretation of Stanley’s renormalising factor. We then study different combinatorial
characteristics of our tree model and finally, we design an efficient uniform random sampler for our tree model based on the classical recursive
generation method.
Origin | Files produced by the author(s) |
---|