Pebbling Number
المؤلف:
Chung, F. R. K
المصدر:
Pebbling in Hypercubes. SIAM J. Disc. Math. 2
الجزء والصفحة:
...
17-5-2022
1531
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  |
![<span style=]() {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:
(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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
