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: 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}, pages = {1197--1217}, publisher = {MathOA foundation}, volume = {2}, number = {6}, year = {2019}, doi = {10.5802/alco.80}, mrnumber = {4049843}, zbl = {07140430}, language = {en}, url = {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] 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] 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] Harmonic morphisms and hyperelliptic graphs, International Math Research Notices (2009), pp. 2914-2955 | Zbl 1178.05031

[4] 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] 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] 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] Treewidth computations II: lower bounds, Information and Computation, Volume 209 (2011), pp. 1103-1119 | Article | MR 2829452 | Zbl 1220.68071

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

[9] A First Course in Graph Theory, Dover books on mathematics, Dover Publications, 2012

[10] 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] 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] 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] Divisors and Sandpiles: An Introduction to Chip-Firing, Amer. Math. Soc., Providence, RI, 2018 | Zbl 1411.05003

[14] 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] 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] Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math., Volume 6 (1939), pp. 239-250 | Numdam | MR 1557026 | Zbl 64.0596.02

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

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

[19] 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] 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] 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] Stable gonality of graphs (2017) (Masters thesis)

[23] Reduced divisors and gonality in finite graphs (2012) (Bachelor’s thesis)

[24] Treewidth is a lower bound on graph gonality (2014) (https://arxiv.org/abs/1407.7055)