Divisorial gonality of graphs

Abstract

In this thesis the concept of divisorial gonality is explored. A triple of distinct definitions for divisorial gonality is presented and they are shown to be equivalent to each other. We explain a number of techniques for reasoning about divisorial gonality. We also consider several simple classes of graphs and calculate their divisorial gonality. We then present an upper bound on divisorial gonality based on minimum cuts between a set of vertices and a single other vertex in the graph.

The main result of this thesis is a set of reduction rules that can be used to recognize the graphs with divisorial gonality at most 2. We prove the rule set is both safe and complete, properties required for it to be usable. We also show that there exists a polynomial time algorithm based on this rule set.

Afterwards we answer three questions about the divisorial gonality of minors and subgraphs by making use of this set of reduction rules. These questions are then also answered for the closely related concepts of stable divisorial gonality and stable gonality.