On Spanning Trees with few Branch Vertices Public
Shull, Warren (Spring 2018)
Abstract
Hamiltonian paths, which are a special kind of spanning tree, have long been of interest in graph theory and are notoriously hard to compute. One notable feature of a Hamiltonian path is that all its vertices have degree at most two in the path. In a tree, we call vertices of degree at least three branch vertices. If a connected graph has no Hamiltonian path, we can still look for spanning trees that come "close," in particular by having few branch vertices (since a Hamiltonian path would have none).
A conjecture of Matsuda, Ozeki, and Yamashita posits that, for any positive integer k, a connected claw-free n-vertex graph G must contain either a spanning tree with at most k branch vertices or an independent set of 2k+3 vertices whose degrees add up to at most n-3. We prove this conjecture, which was known to be sharp.
Table of Contents
1 Introduction: page 1
2 Proof for k=2: page 6
2.1 Lemmas: page 8
2.2 First Structure: page 10
2.3 Second Structure: page 15
2.4 Third Structure: page 22
2.5 Fourth Structure: page 27
2.6 Fifth Structure: page 31
3 General Case: page 35
4 Future Work: page 50
Bibliography: page 51
About this Dissertation
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Mot-clé | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
On Spanning Trees with few Branch Vertices () | 2018-04-05 16:56:05 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|