Graphs of gonality three
Algebraic Combinatorics, Volume 2 (2019) no. 6, p. 1197-1217

In 2013, Chan classified all metric hyperelliptic graphs, proving that divisorial gonality and geometric gonality are equivalent in the hyperelliptic case. We show that such a classification extends to combinatorial graphs of divisorial gonality three, under certain edge- and vertex-connectivity assumptions. We also give a construction for graphs of divisorial gonality three, and provide conditions for determining when a graph is not of divisorial gonality three.

Received : 2018-10-19
Revised : 2019-03-31
Accepted : 2019-04-10
Published online : 2019-12-04
DOI : https://doi.org/10.5802/alco.80
Classification:  14T05,  05C05,  05C57
Keywords: graph gonality, chip-firing, tropical geometry
@article{ALCO_2019__2_6_1197_0,
     author = {Aidun, Ivan and Dean, Frances and Morrison, Ralph and Yu, Teresa and Yuan, Julie},
     title = {Graphs of gonality three},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {2},
     number = {6},
     year = {2019},
     pages = {1197-1217},
     doi = {10.5802/alco.80},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_6_1197_0}
}
Aidun, Ivan; Dean, Frances; Morrison, Ralph; Yu, Teresa; Yuan, Julie. Graphs of gonality three. Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1197-1217. doi : 10.5802/alco.80. https://alco.centre-mersenne.org/item/ALCO_2019__2_6_1197_0/

[1] Baker, Matthew Specialization of linear systems from curves to graphs, Algebra and Number Theory, Volume 2 (2008) no. 6, pp. 613-653 | Article | MR 2448666 | Zbl 1162.14018

[2] Baker, Matthew; Norine, Serguei Riemann–Roch and Abel–Jacobi theory on a finite graph, Advances in Mathematics, Volume 215 (2007), pp. 766-788 | Article | MR 2355607 | Zbl 1124.05049

[3] Baker, Matthew; Norine, Serguei Harmonic morphisms and hyperelliptic graphs, International Math Research Notices (2009), pp. 2914-2955 | Zbl 1178.05031

[4] Baker, Matthew; Shokrieh, Farbod Chip-firing games, potential theory on graphs, and spanning trees, Journal of Combinatorial Theory. Series A, Volume 120 (2013), pp. 164-182 | Article | MR 2971705 | Zbl 1408.05089

[5] Bodewes, Jelco M.; Bodlaender, Hans L.; Cornelissen, Gunther; van der Wegen, Marieke Recognizing Hyperelliptic Graphs in Polynomial Time, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings (2018), pp. 52-64 | Zbl 06982995

[6] Bodlaender, Hans L. Dynamic programming on graphs with bounded treewidth, Automata, languages and programming (Tampere, 1988) (Lecture Notes in Comput. Sci.) Volume 317 (1988), pp. 105-118 | Article | MR 1023630 | Zbl 0649.68039

[7] Bodlaender, Hans L.; Koster, Arie M.C.A. Treewidth computations II: lower bounds, Information and Computation, Volume 209 (2011), pp. 1103-1119 | Article | MR 2829452 | Zbl 1220.68071

[8] Chan, Melody Tropical hyperelliptic curves, Journal of Algebraic Combinatorics, Volume 37 (2013), pp. 331-359 | Article | MR 3011346 | Zbl 1266.14050

[9] Chartrand, Gary; Zhang, Ping A First Course in Graph Theory, Dover books on mathematics, Dover Publications, 2012

[10] Cools, Filip; Draisma, Jan On metric graphs with prescribed gonality, Journal of Combinatorial Theory. Series A, Volume 156 (2018), pp. 1-21 | Article | MR 3762100 | Zbl 1381.05012

[11] Cools, Filip; Draisma, Jan; Payne, Sam; Robeva, Elina A tropical proof of the Brill-Noether theorem, Advances in Mathematics, Volume 230 (2012) no. 2, pp. 759-776 | Article | MR 2914965 | Zbl 1325.14080

[12] Cornelissen, Gunther; Kato, Fumiharu; Kool, Janne A combinatorial Li–Yau inequality and rational points on curves, Mathematische Annalen, Volume 361 (2015), pp. 211-258 | Article | MR 3302619 | Zbl 1341.11034

[13] Corry, Scott; Perkinson, David Divisors and Sandpiles: An Introduction to Chip-Firing, Amer. Math. Soc., Providence, RI, 2018 | Zbl 1411.05003

[14] Dhar, Deepak Self-organized critical state of sandpile automaton models, Physical Review Letters, Volume 64 (1990) no. 14, pp. 1613-1616

[15] Eisenbud, David The geometry of syzygies: a second course in commutative algebra and algebraic geometry, Graduate texts in mathematics, Springer, New York, 2005

[16] Frucht, R. Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math., Volume 6 (1939), pp. 239-250 | Article | MR 1044086 | Zbl 0943.82553

[17] Gathmann, Andreas; Kerber, Michael A Riemann–Roch theorem in tropical geometry, Mathematische Zeitschrift, Volume 259 (2008), pp. 217-230 | Zbl 1066.14001

[18] Gijswijt, Dion Computing divisorial gonality is hard (2015) (https://arxiv.org/abs/1504.06713v1) | MR 1557026 | Zbl 64.0596.02

[19] Luo, Ye Rank-determining sets of metric graphs, Journal of Combinatorial Theory. Series A, Volume 118 (2011), pp. 1775-1793 | Article | MR 2377750 | Zbl 1187.14066

[20] Mikhalkin, Grigory; Zharkov, Ilia Tropical curves, their Jacobians and theta functions, Curves and abelian varieties (Contemp. Math.) Volume 465, Amer. Math. Soc., Providence, RI, 2008, pp. 203-230

[21] Urakawa, Hajime A discrete analogue of the harmonic morphism and Green kernel comparison theorems, Glasg. Math. J., Volume 42 (2000) no. 3, pp. 319-334 | Article | MR 2793609 | Zbl 1227.05133

[22] van der Wegen, Marieke Stable gonality of graphs (2017) (Masters thesis) | Article | MR 2457739 | Zbl 1152.14028

[23] van Dobben de Bruyn, Josse Reduced divisors and gonality in finite graphs (2012) (Bachelor’s thesis) | Article | MR 1793801 | Zbl 1002.05049

[24] van Dobben de Bruyn, Josse; Gijswijt, Dion Treewidth is a lower bound on graph gonality (2014) (https://arxiv.org/abs/1407.7055)