Abstract
dc:description.abstractLet πΊ=(π,πΈ) be a graph and let π be a spanning tree of πΊ. The thinness parameter of π denoted by π(π) is the maximum over all cuts of the proportion of the edges of π in the cut. Thin trees play an important role in some recent papers on the Asymmetric Traveling Salesman Problem (ATSP). Goddyn conjectured that every graph of sufficiently large edge-connectivity has a spanning tree π such that π(π) β€ π. In this thesis, we study the problem of finding thin spanning trees in two families of graphs, namely, (1) distance-regular graphs (DRGs), and (2) planar graphs. For some families of DRGs such as strongly regular graphs, Johnson graphs, Crown graphs, and Hamming graphs, we give a polynomial-time construction of spanning trees π of maximum degree β€ 3 such that π(π) is determined by the parameters of the graph. For planar graphs, we improve the analysis of Merker and Postle ("Bounded Diameter Arboricity", arXiv:1608.05352v1) and show that every 6-edge-connected planar graph has two edge-disjoint spanning trees π,πβ² such that π(π),π(πβ²) β€ 14β15. For 8-edge-connected planar graphs πΊ, we present a simplified version of the techniques of Merker and Postle and show that πΊ has two edge-disjoint spanning trees π,πβ² such that π(π),π(πβ²) β€ 12β13.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Mousavi Haji, Seyyed Ramin
- Advisor dc:contributor.advisor
-
- Cheriyan, Joseph
Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/13174