MATH Seminar

Title: On Spanning Trees with few Branch Vertices
Defense: Dissertation
Speaker: Warren Shull of Emory University
Contact: Warren Shull, warren.edward.shull@emory.edu
Date: 2018-03-05 at 4:00PM
Venue: MSC W301
Download Flyer
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 two in the path. In a tree, we call vertices of degree at least three \emph{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). \bigskip 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$. In other words, $G$ has this spanning tree whenever $\sigma_{2k+3}(G)\geq n-2$. We prove this conjecture, which was known to be sharp.