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.

اخر الاخبار

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

قسم صناعة الشبابيك يستعرض أعماله للمشاركين في البرنامج المركزي الأسبوعي

جامعة الكفيل تنظم حملة للتبرع بالدم للأطفال المصابين بالثلاسيميا والأورام السرطانية

قسم الشؤون الفكرية يصدر العدد 55 من مجلة العميد المحكمة

المجمع العلمي يجري اختبار القبول للمتقدمين إلى دورة ربيع القرآن في كربلاء

المزيد

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

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

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

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

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

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