The stable gonality of finite graphs
Summary
This thesis is devoted to finding a finite algorithm to
calculate the \emph{stable gonality} of graphs. The stable
gonality was first defined by Cornelissen et al. in
\cite{Gunther}. A \emph{finite harmonic morphism} $\vp$ is a
map from a refinement $H$ of a graph $G$ to a tree $T$ obeying
several properties. Together with this comes a map $r_\vp :
E(H)\to \N$ which assigns \emph{indices} to all edges of $H$.
It turns out that we can assign a \emph{degree} to every finite
harmonic morphism. The stable gonality $\sgon(G)$ is the
minimal degree of a finite harmonic morphism from a refinement
of $G$ to a tree.
The naive algorithm to calculate the stable gonality of a graph
does not terminate, because we have to consider all refinements
$H$, all trees $T$ and all maps $r_\vp$, which are three
infinite loops. I describe a new algorithm to calculate
$\sgon(G)$ in finite time, using several new theorems that
reduce the set of refinements and trees we have to consider.
First, I give a bound on the size of $T$ is terms of $G$. Then,
I replace $T$ by a \emph{minor-universal tree} containing all
trees of a given size as a minor. Finally, I prove that we may
assume that the indices of the edges of $H$ have a nice
property, and that they can be bounded from above by $|E(G)|$.