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

gonalitychip-firingdivisor theoryscramble number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57) Graph operations (line graphs, products, etc.) (05C76) 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 Riemann-Roch theorem in tropical geometry
• A combinatorial Li-Yau inequality and rational points on curves
• A new lower bound on graph gonality
• 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

(11)

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

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)