On Spanning Trees with few Branch Vertices Open Access

Shull, Warren (Spring 2018)

Permanent URL: https://etd.library.emory.edu/concern/etds/p2676v52c?locale=en


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

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
  • English
Research Field
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files