Upper bound on the divisorial gonality of a graph
From Egres Open
[math]\rm{gon}(G) \leq \frac{|E(G)|-|V(G)|}{2} + 2 [/math], where [math]\rm{gon}(G)[/math] the denotes the divisorial gonality of graph [math]G[/math].
Remarks
- It is a conjecture of Matthew Baker based on extensive computer calculations by Adam Tart [1].
- In the context of graph divisor theory [math]|E(G)|-|V(G)|+ 1 [/math] is called as the genus of the graph and denoted by [math]g[/math]. Using this notion, the conjecture can be formulated as [math]\rm{gon}(G) \leq \lfloor \frac{g+3}{2} \rfloor [/math], which is the original form of the conjecture, see Conj. 3.10. in [1].
- It is also conjectured in [1] that for each integer [math] g \geq 0 [/math], there exists a graph of genus [math]g[/math] with gonality exactly [math]\lfloor \frac{g+3}{2} \rfloor [/math].
- There is also a more general version of the conjecture in [1], the so-called Brill-Noether Conjecture for Graphs: Fix integers [math]g, r, d \geq 0[/math], and set [math]\varrho(g, r, d) = g − (r + 1)(g − d + r)[/math]. Then:
- (1) If [math]\varrho(g, r, d) \geq 0[/math], then every graph of genus [math]g[/math] has a divisor [math]D[/math] with [math]\rm{rank}(D) = r[/math] and [math]\deg(D) \leq d[/math].
- (2) If [math]\varrho(g, r, d) \lt 0[/math], then there exists a graph of genus [math]g[/math] for which there is no divisor D with [math]\rm{rank}(D) = r[/math] and [math]\deg(D) \leq d[/math].
