Gonality
The gonality (also called divisorial gonality) gon(G) of a (finite) graph G is the minimum degree of a rank 1 divisor on that graph. It can be thought of as the minimum number of chips that can be placed on that graph such that a debt of 1 can be eliminated via "chip-firing moves" over all possible debt placements. Graph gonality was introduced by Baker and Norine (2007, 2009) and is analogous to the theory of divisors on algebraic curves.
The gonality of a graph is one of several graph analogs of the gonality of an algebraic curve, which is the minimum degree of a rational map from the curve to the projective line (Echavarria 2021).
The gonality of a graph and satisfies
| kappa(G)<=lambda(G)<=tw(G)<=sn(G)<=gon(G), |
where kappa(G) is the vertex connectivity, lambda(G) is the edge connectivity, tw(G) is the treewidth, and sn(G) is the scramble number of G (Harp et al. 2020, Echavarria et al. 2021).
Trees have gonality of 1. Gonalities for a number of special classes of graphs are summarized by Echavarria et al. (2021, Examples 2.7 and 2.8).
The gonality of a graph is NP-hard to compute (Gijswijt et al. 2020, Echavarria 2021).
See also
Scramble NumberExplore with Wolfram|Alpha
More things to try:
References
Baker, M. and Norine, S. "Riemann-Roch and Abel-Jacobi Theory on a Finite Graph." Adv. Math. 215, 766-788, 2007.Baker, M. and Norine, S. "Harmonic Morphisms and Hyperelliptic Graphs." Int. Math Res. Not. 1, 2914-2955, 2009.Echavarria, M.; Everett, M.; Huang, R.; Jacoby, L.; Morrison, R.; Weber, B. "On the Scramble Number of Graphs." 29 Mar 2021. https://arxiv.org/abs/2103.15253.Gijswijt, D.; Smit, H.; and van der Wegen, M. "Computing Graph Gonality Is Hard." Disc. Appl. Math. 287, 134-149, 2020.Harp, M.; Jackson, E.; Jensen, D.; and Speeter, N. "A New Lower Bound on Graph Gonality." 1 Jun 2020. https://arxiv.org/abs/2006.01020.Morrison, R. and Tolley, L. "Computing Higher Graph Gonality Is Hard." 6 Aug 2022. https://arxiv.org/abs/2208.03573.Referenced on Wolfram|Alpha
GonalityCite this as:
Weisstein, Eric W. "Gonality." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Gonality.html