2021/03/29 by Echavarria, Marino, Everett, Max, Huang, Robin +3 · 1 citation
#05C57 #14T05 #Algebraic Geometry (math.AG) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.15253
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.