Gonality

The gonality (also called divisorial gonality)  of a (finite) graph  is the minimum degree of a rank 1 divisor on that graph. It can be thought of as the minimum number of chips that can be placed on that graph such that a debt of 1 can be eliminated via "chip-firing moves" over all possible debt placements.

The gonality of a graph is one of several graph analogs of the gonality of an algebraic curve, which is the minimum degree of a rational map from the curve to the projective line (Echavarria 2021).

The gonality of a graph and satisfies

where  is the vertex connectivity,  is the edge connectivity,  is the treewidth, and  is the scramble number of  (Harp et al. 2020, Echavarria et al. 2021).

Trees have gonality of 1. Gonalities for a number of special classes of graphs are summarized by Echavarria et al. (2021, Examples 2.7 and 2.8).

The gonality of a graph is NP-hard to compute (Gijswijt et al. 2020, Echavarria 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.

Gijswijt, D.; Smit, H.; and van der Wegen, M. "Computing Graph Gonality Is Hard." Disc. Appl. Math. 287, 134-149, 2020.

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