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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

خمسون عامًا من العطاء.. نجم الأعرجي خادم الزائرين بلا انقطاع

العتبة العباسية المقدسة تواصل إقامة مجالسها العزائية لإحياء شهر المحرم

العتبة العباسية المقدسة تطلق سلسلة محاضرات قرآنية عاشورائية في بابل

في مساء اليوم الخامس من المحرّم.. المواكب الكربلائيّة تواصل فعالياتها العزائية

المزيد

الآخبار الصحية

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

الآخبار التكنلوجية

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength