The gonality (also called divisorial gonality) 
of a nonempty finite connected
graph 
with no loops, allowing multiple
edges, is the minimum degree of a rank 1 graph
divisor. It can be thought of as the minimum number
of chips that can be placed on that graph such that a debt
of 1 can be eliminated via "chip-firing moves" over all possible debt placements.
Graph gonality was introduced by Baker and Norine (2007, 2009) and is analogous to
the theory of divisors on algebraic curves.
The gonality of a graph is one of several graph analogs of the gonality of a smooth projective algebraic curve, which is the minimum degree of a nonconstant rational map from the curve to the projective line (Echavarria et al. 2022).
For a finite connected graph 
that is a simple graph, its
gonality satisfies
 |
where 
is the vertex
connectivity, 
is the edge connectivity, 
is the treewidth, and 
is the scramble
number of 
(Harp et al. 2022, Echavarria et al. 2022).
Trees have gonality of 1. Gonalities for a number of special classes of graphs are summarized by Echavarria et al. (2022).
The gonality of a graph is NP-hard to compute (Gijswijt et al. 2020, Echavarria et al. 2022).
