Labeled Trees and Spanning Trees: Computational Discrete Mathematics and Applications

<p>In this thesis, we examine two topics. In the first part, we consider Leech tree which is a tree of order n with positive integer edge weights such that the weighted distances between pairs of vertices are exactly from 1 to n choose 2. Only five Leech trees are known and some non-existence results have been presented through the years. Variations of Leech trees such as the minimal distinct distance trees and modular Leech trees have been considered in recent years. In this thesis, such Leech-type questions on distances between leaves are studied as well as some other labeling questions related to the original motivation for Leech trees. As a second part, we consider the question of finding spanning trees under various restrictions is studied. A “dense” tree, from graph theoretical point of view, has small total distances between vertices and large number of substructures. In this thesis, the “density” of a spanning tree is conveniently measured by the total distance of the tree. By utilizing established conditions and relations between trees with the minimum total distance, an edge-swap heuristic for generating “dense” spanning trees is presented.</p>

Name thesis:degree_name

Master of Science in Mathematics (M.S.)

Level thesis:degree_level

Thesis (open access)

Discipline thesis:degree_discipline

Department of Mathematical Sciences

Year dc:date.available

2015

Author dc:creator

• Yalman, Demet

Contributors dc:contributor

• Colton Magnant
• Goran Lesaja

• ETD
• Edge-swap heuristic
• Dense tree
• Minimum spanning tree
• Leech tree
• Modular Leech tree
• Distances between leaves
• Discrete Mathematics and Combinatorics

Repository record dc:identifier

https://digitalcommons.georgiasouthern.edu/etd/1297

OAI identifier oai:identifier

oai:digitalcommons.georgiasouthern.edu:etd-2364