Divisorial gonality of a graph

From Egres Open
Jump to: navigation, search

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

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