# wHw141񉞐kb̂m点

1999N 730 (j) 16:00--17:00
u
p(KIM Ju-Young)i緝JgbN(Catholic){Zj
The Pebbling Numbers of Some Graphs
v|
Chung [Pebbling in hypercubes, SIAM J. Discrete Math. 2 (4) (1989) 467-472] has defined a pebbling move on a graph G to be the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. A pebble means a small stone. The pebbling number f(G) of a connected graph is the least number of pebbles such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex. Graham proposed a conjecture that for any connected graphs G and H,f(G~H)\leq f(G)f(H) where G~H is the product of two graphs G and H. Moews [Pebbling graphs, J. Combin. Theory Ser. B 55 (1992) 244-252] confirmed this conjecture for trees. Some mathematicians proved that Graham's conjecture for the following cases.
1. G is an even cycle and H satisfies the two-pebbling property
2. G and H are both odd cycle, and one of them has at least 15 vertices
3. G=H=C5.
In this talk we show that Graham's conjecture holds when G=H=K2,3 and G=H=K3,3.
ȊwȑZ~i[iHwcbTKTOPj
A
840-8502 s{P wHwȊw
O [nakahara]
FAX 0952(28)8501~TEL 0952(28)8529

140̂m点; 142̂m点
kb̂m点̃y[Wɖ߂
ȊwȂ̃z[y[Wɖ߂