Scramble Number
The scramble number sn(G) of a graph G is a graph invariant developed to aid in the study of gonality of graphs. The scramble number is NP-hard to compute (Echavarria et al. 2021).
The scramble number satisfies
| sn(G)>=min(lambda(G),|V(G)|), |
where lambda(G) is the edge connectivity and |V(G)| is the vertex count of G.
The scramble number is the most powerful known lower bound on the gonality of a graph and satisfies
| kappa(G)<=lambda(G)<=tw(G)<=sn(G)<=gon(G), |
where kappa(G) is the vertex connectivity, lambda(G) is the edge connectivity, tw(G) is the treewidth, and gon(G) is the gonality of G (Harp et al. 2020, Echavarria et al. 2021).
Unfortunately, the scramble number is not quite as well-behaved as treewidth (Echavarria et al. 2021).
The scramble number of the KC graph K_n square C_r with n>=2 and r>=4 is min(2n,r(n-1)) (Echavarria et al. 2021).
See also
Gonality, Pebbling NumberExplore with Wolfram|Alpha
More things to try:
References
Echavarria, M.; Everett, M.; Huang, R.; Jacoby, L.; Morrison, R.; Weber, B. "On the Scramble Number of Graphs." 29 Mar 2021. https://arxiv.org/abs/2103.15253.Harp, M.; Jackson, E.; Jensen, D.; and Speeter, N. "A New Lower Bound on Graph Gonality." 1 Jun 2020. https://arxiv.org/abs/2006.01020.Referenced on Wolfram|Alpha
Scramble NumberCite this as:
Weisstein, Eric W. "Scramble Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ScrambleNumber.html