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.
- It is known that the rank of a graph divisor stays the same if each edge is subdivided by [math]k[/math] new points and 0 is placed on the new points[4]. Similarly, it was conjectured by Baker that the gonality of a graph stays the same if each edge is subdivided by [math]k[/math] new points[5]. This turned out to be false[6]. However, it is still not completely understood how gonality behaves with respect to edge subdivisions.
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
- ↑ Hladky, Král, Norine, Rank of divisors on tropical curves, Journal of Combinatorial Theory, Series A, Volume 120, Issue 7, September 2013, Pages 1521-1538 Link
- ↑ Matthew Baker. Specialization of linear systems from curves to graphs. Algebra & NumberTheory, 2(6):613–653, 2008.
- ↑ Josse van Dobben de Bruyn, Harry Smit, Marieke van der Wegen, Discrete and metric divisorial gonality can be different (2021) ArXiv Link
