A note on optimal pebbling of hypercubes

被引:7
作者
Fu, Hung-Lin [1 ]
Huang, Kuo-Ching [2 ]
Shiue, Chin-Lin [3 ]
机构
[1] Natl Chiao Tung Univ, Dept Appl Math, Hsinchu 30050, Taiwan
[2] Providence Univ, Dept Financial & Computat Math, Taichung 43301, Taiwan
[3] Chung Yuan Christian Univ, Dept Appl Math, Chungli, Taiwan
关键词
Optimal pebbling; Hypercubes; NUMBER; GRAPHS;
D O I
10.1007/s10878-012-9492-9
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
A pebbling move consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. If a distribution delta of pebbles lets us move at least one pebble to each vertex by applying pebbling moves repeatedly(if necessary), then delta is called a pebbling of G. The optimal pebbling number f'(G) of G is the minimum number of pebbles used in a pebbling of G. In this paper, we improve the known upper bound for the optimal pebbling number of the hypercubes Q (n) . Mainly, we prove for large n, by a probabilistic argument.
引用
收藏
页码:597 / 601
页数:5
相关论文
共 12 条
[1]  
Chung F., 1989, SIAM Journal on Discrete Mathematics, V2, P467, DOI [10.1137/0402041, DOI 10.1137/0402041]
[2]  
Clarke TA, 1997, J GRAPH THEOR, V25, P119, DOI 10.1002/(SICI)1097-0118(199706)25:2<119::AID-JGT3>3.3.CO
[3]  
2-#
[4]   The optimal pebbling number of the complete m-ary tree [J].
Fu, HL ;
Shiue, CL .
DISCRETE MATHEMATICS, 2000, 222 (1-3) :89-100
[5]   The pebbling number of C5 x C5 [J].
Herscovici, DS ;
Higgins, AW .
DISCRETE MATHEMATICS, 1998, 187 (1-3) :123-135
[6]   AN ADDITION THEOREM ON THE INTEGERS MODULO N [J].
LEMKE, P ;
KLEITMAN, D .
JOURNAL OF NUMBER THEORY, 1989, 31 (03) :335-345
[7]  
MacWillians FJ, 1977, THEORY ERROR CORRECT
[8]   PEBBLING GRAPHS [J].
MOEWS, D .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1992, 55 (02) :244-252
[9]   Optimally pebbling hypercubes and powers [J].
Moews, D .
DISCRETE MATHEMATICS, 1998, 190 (1-3) :271-276
[10]  
Pachter L., 1995, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), V107, P65