Multiplicity-free gonality on graphs
Abstract
The divisorial gonality of a graph is the minimum degree of a positive rank divisor on that graph. We introduce the multiplicity-free gonality of a graph, which restricts our consideration to divisors that place at most 1 chip on each vertex. We give a sufficient condition in terms of vertex-connectivity for these two versions of gonality to be equal; and we show that no function of gonality can bound multiplicity-free gonality, even for simple graphs. We also prove that multiplicity-free gonality is NP-hard to compute, while still determining it for graph families for which gonality is currently unknown. We also present new gonalities, such as for the wheel graphs.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2023.11.2.2
References
I. Aidun, F. Dean, R. Morrison, T. Yu, and J. Yuan. Gonality sequences of graphs. SIAM J. Discrete Math. 35 (2) (2021), 814–839.
I. Aidun and R. Morrison. On the gonality of Cartesian products of graphs. Electron. J. Combin. 27 (4) (2020), #P4.52.
S. Backman. Riemann-Roch theory for graph orientations. Adv. Math. 309 (2017), 655–691.
M. Baker. Specialization of linear systems from curves to graphs. Algebra Number Theory 2 (6) (2008), 613–653. With an appendix by Brian Conrad.
M. Baker and S. Norine. Riemann-Roch and Abel-Jacobi theory on a finite graph. Adv. Math. 215 (2) (2007), 766–788.
M. Baker and S. Norine. Harmonic morphisms and hyperelliptic graphs. Int. Math. Res. Not. IMRN 15 (2009), 2914–2955.
G. Cornelissen, F. Kato, and J. Kool. A combinatorial Li-Yau inequality and rational points on curves. Math. Ann. 361 (1-2) (2015), 211–258.
A. Deveau, D. Jensen, J. Kainic, and D. Mitropolsky. Gonality of random graphs. Involve 9 (4) (2016), 715–720.
D. Dhar. Self-organized critical state of sandpile automaton models. Phys. Rev. Lett. 64 (14) (1990), 1613–1616.
M. Echavarria, M. Everett, R. Huang, L. Jacoby, R. Morrison, and B. Weber. On the scramble number of graphs. Discrete Appl. Math. 310 (2022), 43–59.
D. Gijswijt, H. Smit, and M. van der Wegen. Computing graph gonality is hard. Discrete Appl. Math. 287 (2020), 134–149.
N. Speeter. The gonality of rook graphs, preprint, 2022.
J. van Dobben de Bruyn. Reduced divisors and gonality in finite graphs. Bachelor’s thesis, Mathematisch Instituut, Universiteit Leiden, 2012.
J. van Dobben de Bruyn and D. Gijswijt. Treewidth is a lower bound on graph gonality. Algebr. Comb. 3 (4) (2020), 941–953.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.