佐賀大学理工学部
第141回応数談話会のお知らせ

日時

1999年 7月30日 (金曜日) 16:00--17:00

講演者

金 珠英(KIM Ju-Young)氏（大邱曉星カトリック(Catholic)大學校）

題目

The Pebbling Numbers of Some Graphs

要旨

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=C₅.

In this talk we show that Graham's conjecture holds when G=H=K_2,3 and G=H=K_3,3.

場所

数理科学科大セミナー室（理工学部ＤＣ棟５階５０１）

連絡先

〒840-8502 佐賀市本庄町１ 佐賀大学理工学部数理科学科
中原 徹 [nakahara＠]
FAX 0952(28)8501~TEL 0952(28)8529