On the scramble number of graphs

DOI10.1016/J.DAM.2021.12.009zbMATH Open1482.05230arXiv2103.15253OpenAlexW4206089437WikidataQ131520141 ScholiaQ131520141MaRDI QIDQ2074355FDOQ2074355

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)

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.

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

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

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)

Cites Work

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

Cited In (11)

• Computing graph gonality is hard
• Title not available (Why is that?)
• 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)