A new lower bound on graph gonality

DOI10.1016/J.DAM.2021.11.003MaRDI QIDQ2065783zbMATH OpenOpenAlexFDO

Authors Michael Harp, Elijah Jackson, David Jensen, Noah Speeter

Publication date 13 January 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.01020

zbMATH Keywords

chip-firinggonalitytreewidth

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We define a new graph invariant called the scramble number. We show that the scramble number of a graph is a lower bound for the gonality and an upper bound for the treewidth. Unlike the treewidth, the scramble number is not minor monotone, but it is subgraph monotone and invariant under refinement. We compute the scramble number and gonality of several families of graphs for which these invariants are strictly greater than the treewidth.

Recommendations

• Graphs of scramble number two
• On the scramble number of graphs
• Treewidth is a lower bound on graph gonality
• Sparse graphs of high gonality
• Constructing tree decompositions of graphs with bounded gonality

Cites work

• A tropical proof of the Brill-Noether theorem
• Computing graph gonality is hard
• Degeneration of linear series from the tropical point of view and applications
• Gonality of expander graphs
• Gonality of random graphs
• Graph searching and a min-max theorem for tree-width
• On the gonality of Cartesian products of graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Sparse graphs of high gonality
• Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
• Treewidth and gonality of glued grid graphs
• Treewidth is a lower bound on graph gonality

Cited in

(9)

• On the scramble number of graphs
• Treewidth is a lower bound on graph gonality
• scientific article; zbMATH DE number 3989382 (Why is no real title available?)
• A Spectral Lower Bound for the Divisorial Gonality of Metric Graphs
• Uniform scrambles on graphs
• Graphs of scramble number two
• Divisorial and geometric gonality of higher-rank tropical curves
• Fibonacci sumsets and the gonality of strip graphs
• Scramble number and tree-cut decompositions

This page was built for publication: A new lower bound on graph gonality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065783)