Pebbling Number

 

Define a pebbling move as a transer of two pebbles from one vertex of a graph edge to an adjacent vertex with one of the pebbles being removed in transit as a toll. The pebbling number  of a graph  is the smallest  such that every supply of  pebbles can satisfy every demand of one pebble (Hurlbert 2011). Computing the pebbling number is NP-complete (Hurlbert 2011).

The values of the pebbling number for various classes of graphs are given in the table below (Hurlbert).

graph	pebbling number
complete bipartite graph
complete graph
cycle graph	{2^(n/2) for n even; (2^((n+3)/2)-1)/3 for n odd" src="https://mathworld.wolfram.com/images/equations/PebblingNumber/Inline10.svg" style="height:69px; width:184px" />
hypercube graph
path graph

The pebbling number satisfies a number of bounds. Let  be the vertex count,  the graph diameter, and  the domination number of a graph .

Breadth lower bounds:

(1)

Cut lower bound (which  contained a cut vertex ):

(2)

Depth lower bound:

(3)

Pigeonhole upper bound:

(4)

Sharper bounds:

			(5)
			(6)
			(7)

(Hurlbert).

For a graph with ,

(8)

where  is the vertex count of  (Hurlbert 2011).

---

REFERENCES

Chung, F. R. K. "'Pebbling in Hypercubes." SIAM J. Disc. Math. 2, 467-472, 1989.

Hurlbert, G. "A Linear Optimization Technique for Graph Pebbling." 28 Jan 2011. https://arxiv.org/abs/1101.5641.

Hurlbert, G. "General Graph Pebbling." Disc. Appl. Math. 161, 1221-1231, 2013.

Hurlbert, G. "Graph Pebbling Numbers Page." http://www.people.vcu.edu/~ghurlbert/pebbling/pnummain.html.

Milans, K. and Clark, B. "The Complexity of Graph Pebbling." SIAM J. Disc. Math. 20, 769-798, 2006.

اخر الاخبار

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

العتبة العباسية المقدسة تواصل تنظيم مجالس العزاء الصباحية بذكرى زيارة عاشوراء

مواكب العزاء تستذكر في التاسع من شهر المحرم شهادة عبدالله الرضيع بن الحسين (عليهما السلام)

العتبة العباسية المقدسة تستذكر تضحيات القاسم بن الحسن (عليهما السلام)

شعبة الحرم الشريف تواصل تنفيذ خطتها الخاصة بشهر المحرّم داخل مرقد أبي الفضل العباس (عليه السلام)

المزيد

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

لهذا السبب.. إغلاق 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