Georgia Institute of Technology
On the independent spanning tree conjectures and related problems
Abstract
dc:description.abstractWe 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 × 12Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/61777