Back to search

University of Waterloo

Thin Trees in Some Families of Graphs

Abstract

dc:description.abstract

Let 𝐺=(𝑉,𝐸) 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

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Mousavi Haji, Seyyed Ramin. Thin Trees in Some Families of Graphs. University of Waterloo, 2018. http://hdl.handle.net/10012/13174