Back to search

Georgia Institute of Technology

On the independent spanning tree conjectures and related problems

Abstract

dc:description.abstract

We say that trees with common root are (edge-)independent if, for any vertex in their intersection, the paths to the root induced by each tree are internally (edge-)disjoint. The relationship between graph (edge-)connectivity and the existence of (edge-)independent spanning trees is explored. The (Edge-)Independent Spanning Tree Conjecture states that every k-(edge-)connected graph has k-(edge-)independent spanning trees with arbitrary root. We prove the case k = 4 of the Edge-Independent Spanning Tree Conjecture using a graph decomposition similar to an ear decomposition, and give polynomial-time algorithms to construct the decomposition and the trees. We provide alternate geometric proofs for the cases k = 3 of both the Independent Spanning Tree Conjecture and Edge-Independent Spanning Tree Conjecture by embedding the vertices or edges in a 2-simplex, and conjecture higher-dimension generalizations. We provide a partial result towards a generalization of the Independent Spanning Tree Conjecture, in which local connectivity between the root and a vertex set S implies the existence of trees whose independence properties hold only in S. Finally, we prove and generalize a theorem of Györi and Lovász on partitioning a k-connected graph, and give polynomial-time algorithms for the cases k = 2, 3, 4 using the graph decompositions used to prove the corresponding cases of the Independent Spanning Tree Conjecture.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hoyer, Alexander
Advisor dc:contributor.advisor
  • Thomas, Robin
Committee members dc:contributor.committeemember
  • Tetali, Prasad
  • Warnke, Lutz
  • Yu, Xingxing
  • Vempala, Santosh

Subjects

dc:subject × 12

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/61777

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hoyer, Alexander. On the independent spanning tree conjectures and related problems. Doctoral thesis, Georgia Institute of Technology, 2019. http://hdl.handle.net/1853/61777