Pebbling and optimal pebbling in graphs
Pebbling and optimal pebbling in graphs
复制标题
DOI：
10.1002/jgt.20278
复制
发表时间：
2005-10
影响因子：
0.9
通讯作者：
David P. Bunde;E. Chambers;D. Cranston;K. Milans;D. West
中科院分区：
文献类型：
--
作者：
David P. Bunde;E. Chambers;D. Cranston;K. Milans;D. West
给定图G的顶点上的鹅卵石分布，鹅卵石移动从一个顶点取出两个鹅卵石，并将一个放在相邻的顶点上。卵石数是最小的k，使得对于每个k个卵石的分布和每个顶点r，一个卵石可以移动到r。最优pebbling数是最小的k，使得k个pebbles的某种分布允许到达每个顶点。
Given a distribution of pebbles on the vertices of a graph G, a pebbling move takes two pebbles from one vertex and puts one on a neighboring vertex. The pebbling number Π(G) is the least k such that for every distribution of k pebbles and every vertex r, a pebble can be moved to r. The optimal pebbling number ΠOPT(G) is the least k such that some distribution of k pebbles permits reaching each vertex.