# ALGEBRAIC COMBINATORICS

Graphs of gonality three
Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 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.

Revised:
Accepted:
Published online:
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},
pages = {1197--1217},
publisher = {MathOA foundation},
volume = {2},
number = {6},
year = {2019},
doi = {10.5802/alco.80},
mrnumber = {4049843},
zbl = {07140430},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.80/}
}
TY  - JOUR
AU  - Aidun, Ivan
AU  - Dean, Frances
AU  - Morrison, Ralph
AU  - Yu, Teresa
AU  - Yuan, Julie
TI  - Graphs of gonality three
JO  - Algebraic Combinatorics
PY  - 2019
DA  - 2019///
SP  - 1197
EP  - 1217
VL  - 2
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.80/
UR  - https://www.ams.org/mathscinet-getitem?mr=4049843
UR  - https://zbmath.org/?q=an%3A07140430
UR  - https://doi.org/10.5802/alco.80
DO  - 10.5802/alco.80
LA  - en
ID  - ALCO_2019__2_6_1197_0
ER  - 
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/articles/10.5802/alco.80/

[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 | Article | MR 1044086 | Zbl 0943.82553

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

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

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

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

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

[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 | Article | MR 2457739 | Zbl 1152.14028

[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 1793801 | Zbl 1002.05049

[22] van der Wegen, Marieke Stable gonality of graphs (2017) (Masters thesis)

[23] van Dobben de Bruyn, Josse Reduced divisors and gonality in finite graphs (2012) (Bachelor’s thesis)

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

Cited by Sources: