| dc.description.abstract | Trees in which edges are oriented from a vertex of lower label towards a vertex
of higher label, commonly referred to as locally oriented trees, were introduced
by Du and Yin in an attempt to solve a problem conjectured by Ethan Cotterill
in his study of secant planes in Algebraic Geometry. Du and Yin, Shin and Zeng,
and StephanWagner provided proofs for a formula which counts the number of
locally oriented trees with a given indegree sequence. Recent studies have concentrated
on finding the number of these trees in which both indegree and outdegree
sequences are simultaneously given. In this thesis, formulas for the number
of locally oriented trees with one source and given outdegree sequences are obtained.
Moreover, reachability questions on vertices of locally oriented trees and
locally oriented noncrossing trees (first studied by Okoth) have been extensively
answered though equivalent results for locally oriented ordered trees had not
been obtained. The purpose of this study was to enumerate trees with local orientation
by indegree and outdegree sequences as well as reachability of vertices.
The specific objectives were; to establish a closed formula for the number of locally
oriented trees whose indegree and outdegree sequences are simultaneously
given and, to determine formulas counting the number of reachable vertices in
labelled ordered trees with local orientation according to path lengths, first children,
non-first children, sinks, leaf sinks, non-leaf sinks and left most paths. To
achieve the first objective, we used induction approach as well as construction
approach to develop recurrence relations. We then used generating functions to
find closed formulas. For the second objective, we used construction approach
of Seo and Shin, recurrence relations, generating functions and direct proofs. We
have obtained closed formulas for reachable vertices in labelled plane trees with
respect to: path lengths, sinks, leaf sinks, left most path, first children, non first
children and non leaf sinks. The results obtained in this work will add to the already
existing literature in this area of research and will also be of importance to
computer scientists as most data in computers are stored in form of plane trees. | en_US |
