Seitz, G. (2011). Analysis of various parameters in labelled trees and tree-like structures [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-53297
E104 - Institut für Diskrete Mathematik und Geometrie
-
Date (published):
2011
-
Number of Pages:
137
-
Keywords:
markierte Bäume; baumartige Strukturen; k-dimensionale Bäume; Inversionen; Vorfahren; Nachkommen; Gradverteilung; lokale Minima
de
labelled trees; tree-like structures; k-trees; inversions; ancestors; descendants; degree distribution; local minima
en
Abstract:
We analyse various parameters in labelled trees (i.e. in trees in which the nodes are labelled with distinct integers) and, more generally, in labelled tree-like graph structures. In trees, we consider two parameters which have already been extensively studied in finite sequences (especially in permutations), namely the number of inversions and the number of local minima. We analyse the behaviour of these quantities in random trees of various labelled tree families. Moreover, we consider a class of graphs known as k-trees. These are graphs with a tree-like structure, which can be constructed by a certain randomised graph evolution process, and which can be seen as a simple model for the growth of complex networks. In these graphs, we study parameters which have already been analysed in ordinary trees, namely the number of ancestors and descendants of nodes and the degree distribution. By the use of generating functions we obtain to a large extent very precise results on the exact distribution of these quantities if the size of the considered random objects is fixed. Apart from that, we can characterize the limiting behaviour of each of these quantities as the size of the considered objects tends to infinity.