Divisorial gonality of a graph

The divisorial gonality $$\rm{gon}(G)$$ of a graph $$G$$ is the smallest degree of a divisor of positive rank in the sense of Baker-Norine.

Remarks

• It is easy to see that $$\rm{gon}(G) = 1$$ if and only if $$G$$ is a tree. For more interesting special cases, see .
• In , Gijswijt proved that computing divisorial gonality is NP-hard (even in the case of simple undirected graphs).
• In , de Bruyn and Gijswijt established a nice lower bound on the gonality of a graph: $$\rm{gon}(G) \ge \rm{tw}(G)$$ , where $$\rm{tw}(G)$$ denotes the treewidth of graph $$G$$ .
• It would be interesting to establish an upper bound on the divisorial gonality of a graph.
• It is known that the rank of a graph divisor stays the same if each edge is subdivided by $$k$$ new points and 0 is placed on the new points. Similarly, it was conjectured by Baker that the gonality of a graph stays the same if each edge is subdivided by $$k$$ new points. This turned out to be false. However, it is still not completely understood how gonality behaves with respect to edge subdivisions.