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.

Received:
Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/alco.80
Classification: 14T05,  05C05,  05C57
Keywords: graph gonality, chip-firing, tropical geometry
Aidun, Ivan 1; Dean, Frances 2; Morrison, Ralph 2; Yu, Teresa 3; Yuan, Julie 4

1. Oberlin College Department of Mathematics 10 N. Professor St. Oberlin OH 44074, USA
2. Williams College Department of mathematics and statistics 33 Stetson Ct. Williamstown MA 01267, USA
3. Williams College Department of mathematics and statistics 33 Stetson Ct. Williamstown MA 01267 USA
4. University of Minnesota-Twin Cities School of mathematics 206 Church St SE Minneapolis MN 55455, USA
@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  - 
%0 Journal Article
%A Aidun, Ivan
%A Dean, Frances
%A Morrison, Ralph
%A Yu, Teresa
%A Yuan, Julie
%T Graphs of gonality three
%J Algebraic Combinatorics
%D 2019
%P 1197-1217
%V 2
%N 6
%I MathOA foundation
%U https://doi.org/10.5802/alco.80
%R 10.5802/alco.80
%G en
%F 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/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: