| dc.description.abstract | This thesis consists of two parts: The first one is concerned with the
theory and applications of regular configurations; the second one is devoted
to TBR graphs.
In the first part, a new approach is proposed to study regular configurations,
an extremal arrangement of necklaces formed by a given number
of red beads and black beads. We first show that this concept is closely related
to several other concepts studied in the literature, such as balanced
words, maximally even sets, and the ground states in the Kawasaki-Ising
model. Then we apply regular configurations to solve the (vertex) cycle
packing problem for shift digraphs, a family of Cayley digraphs.
TBR is one of widely used tree rearrangement operationes, and plays
an important role in heuristic algorithms for phylogenetic tree reconstruction.
In the second part of this thesis we study various properties
of TBR graphs, a family of graphs associated with the TBR operation.
To investigate the degree distribution of the TBR graphs, we also study
-index, a concept introduced to measure the shape of trees. As an interesting
by-product, we obtain a structural characterization of good trees,
a well-known family of trees that generalizes the complete binary trees. | en_US |
