TOPICS
Search

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).


See also

Gonality, Pebbling Number

Explore with Wolfram|Alpha

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.

Cite this as:

Weisstein, Eric W. "Scramble Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ScrambleNumber.html

Subject classifications