Scramble Number
المؤلف:
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.
الجزء والصفحة:
...
17-5-2022
1573
Scramble Number
The scramble number 
of a graph 
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
where 
is the edge connectivity and 
is the vertex count of 
.
The scramble number is the most powerful known lower bound on the gonality of a graph and satisfies
where 
is the vertex connectivity, 
is the edge connectivity, 
is the treewidth, and 
is the gonality of 
(Harp et al. 2020, Echavarria et al. 2021).
Unfortunately, the scramble number is not quite as well-behaved as treewidth (Echavarria et al. 2021).
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
