On the scramble number of graphs

DOI10.1016/J.DAM.2021.12.009MaRDI QIDQ2074355zbMATH OpenOpenAlexWikidataFDO

Authors Marino Echavarria, Max Everett, Robin Huang, Liza Jacoby, Ralph Morrison, Ben Weber

Publication date 9 February 2022

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

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

zbMATH Keywords

chip-firingdivisor theorygonalityscramble number

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph operations (line graphs, products, etc.) (05C76) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Games involving graphs (91A43)

Abstract: The scramble number of a graph is an invariant recently developed to aid in the study of divisorial gonality. In this paper we prove that scramble number is NP-hard to compute, also providing a proof that computing gonality is NP-hard even for simple graphs, as well as for metric graphs. We also provide general lower bounds for the scramble number of a Cartesian product of graphs, and apply these to compute gonality for many new families of product graphs.

Recommendations

• Graphs of scramble number two
• A new lower bound on graph gonality
• Computing graph gonality is hard
• Computing the Scattering Number of Graphs
• Stable divisorial gonality is in NP

Cites work

• A combinatorial Li-Yau inequality and rational points on curves
• A new lower bound on graph gonality
• A Riemann-Roch theorem in tropical geometry
• A tropical proof of the Brill-Noether theorem
• Chip-firing games on graphs
• Computing graph gonality is hard
• Connectivity of Cartesian products of graphs
• Gonality of random graphs
• Gonality sequences of graphs
• Graph minors. III. Planar tree-width
• Graph searching and a min-max theorem for tree-width
• Graphs of gonality three
• Harmonic Morphisms and Hyperelliptic Graphs
• On the gonality of Cartesian products of graphs
• Rank-determining sets of metric graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Riemann-Roch theory for graph orientations
• Self-organized critical state of sandpile automaton models
• Self-organized criticality
• Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
• The Geometry of Syzygies
• Treewidth and gonality of glued grid graphs
• Treewidth is a lower bound on graph gonality
• Tropical curves, their Jacobians and theta functions

Cited in

(12)

• Fast scramblers, horizons and expander graphs
• Computing graph gonality is hard
• A new lower bound on graph gonality
• Discrete and metric divisorial gonality can be different
• scientific article; zbMATH DE number 5925154 (Why is no real title available?)
• Scrambled sets and chain recurrence points of generic graph maps
• Stable divisorial gonality is in NP
• Uniform scrambles on graphs
• Multiplicity-free gonality on graphs
• Graphs of scramble number two
• The gonality of queen's graphs
• Scramble number and tree-cut decompositions

This page was built for publication: On the scramble number of graphs

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