圓石分配圖的研究

A Study on the Optimal Pebbling of Graphs

吳柏翰

指導教授 ： 蔡孟傑

國立清華大學/理學院/數學系/碩士(2013年)

摘要

一步圓石移動(pebbling move)定義為將兩個圓石從一個點上拿起，丟掉一個，並將另一個放到相鄰的點上。一個圖G的配置或分配(configuration or distribution) C是一個從V(G)映至非負整數的函數。我們讓C(v)是點v所被分配的圓石數，所以G上的圓石總數為v∈V(G)C(v)。若一個配置C讓我們藉由重覆的(若有需要)圓石移動移動至少一個圓石到任意一點上，則C被稱為一個G的圓石分配(pebbling)。G的最優圓石分配數(optimal pebbling number) f’(G)是一個使用最少圓石的G的圓石分配之圓石總數。
　　有許多方法能處理這個問題，例如機率[6]、錯誤更正碼[9]或特殊類型的控制集[6]。此篇論文主要關心兩個圖相乘的最優圓石分配數。我們得到了f’(P3 × Pn)、f’(Q3) = f’(P2 × Q2) = f’(P2 × C4)、f’(Q4) = f’(P2 × Q3)和f’(Q5) = f’(P2 × Q4)的值。對於一般化的圖，給了一些上界。我們也提供了不同的方法證明f’(Pn)及f’(P2 × Pn)的值。

關鍵字

圓石移動 ； 配置 ； 分配 ； 圓石分配 ； 最優圓石分配數

參考文獻

and optimal pebbling in graphs, J. Graph Theory 57, 2008, 215-238.

[2] F. R. K. Chung, Pebbling in hypercubes, SIAM J. Disc. Math, Vol. 2, no. 4,

1989, 467-472.

[3] T. A. Clarke, R. A. Hochberg and G. H. Hurlbert, Pebbling in diameter two

[4] R. Feng and J. Y. Kim, Graham's pebbling conjecture on product of complete