# Divisorial gonality of a graph

From Egres Open

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

## Remarks

- It is easy to see that [math]\rm{gon}(G) = 1[/math] if and only if [math]G[/math] is a tree. For more interesting special cases, see
^{[1]}. - In
^{[2]}, Gijswijt proved that computing divisorial gonality is NP-hard (even in the case of simple undirected graphs). - In
^{[3]}, de Bruyn and Gijswijt established a nice lower bound on the gonality of a graph: [math] \rm{gon}(G) \ge \rm{tw}(G) [/math], where [math]\rm{tw}(G) [/math] denotes the treewidth of graph [math]G[/math]. - It would be interesting to establish an upper bound on the divisorial gonality of a graph.

### References

- ↑ , Reduced divisors and gonality in finite graphs, Bachelor's Thesis (2012) Link
- ↑ , Computing divisorial gonality is hard, (2015) ArXiv Link
- ↑ , Treewidth is a lower bound on graph gonality, (2014) ArXiv Link