圖的臨界圓石分配數

Abstract

給定一個圖G，我們將圓石放在圖G上的點，一步圓石移動定義為從G 上的一點v拿兩顆圓石然後放一個到與v相鄰的點。如果G上的一個圓石分配方式D，我們可以經由一序列的圓石移動後，對於任一G中被選定的點會存在至少有一顆圓石，則我們稱這個分配方式D為可以解的。一連通圖G上的圓石分配數f(G)是最少的圓石數，使得對於在G 上含有f(G)個圓石數的每種分配方式都是可以解的。如果G上的一個圓石分配方式D，我們可以經由一序列的圓石移動後，對於G中被選定的點r 會存在至少有一顆圓石，則我們稱這個分配方式D為r-可以解的。一連通圖G上的臨界圓石分配數cr(G)是對於G上任何有選定分配方式中最小r-可以分解的最大圓石數。 在此篇論文當中，我們首先從圓石分配數中的研究當中，整理出一些已知的性質，然後我們也得到一些關於臨界圓石數的新結果，其中包括圈，樹圖，彼得森圖及一些乘積圖等等的臨界圓石數。

Given a distribution of pebbles on the vertices of a graph G, a pebbling step (or pebbling move) takes two pebbles from one vertex and place one pebble on an adjacent vertex. A distribution D of pebbles on the graph G is called solvable if, starting from D, it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number f(G) of a connected graph is the smallest number of pebbles such that every distribution with f(G) pebbles on G is solvable. A distribution D is r-solvable if there exists a sequence of pebbling steps which begin from D and end in at least one pebble on the vertex r. The r-critical pebbling number cr(G) is the largest size of a minimally r-solvable rooted distribution on G for any r. In this thesis, we first derive several known results from the study of pebbling numbers, and then we also obtain several new results on critical pebbling numbers. The results are (1) cr(Cm) = f(Cm)-1 if m_3 (mod 4), and f(Cm) otherwise; (2) cr(T) = 2d, where T is a tree and d is the diameter of T; (3) cr(P) = 6, where P is the Petersen graph; (4) cr(Qn) = 2n, where Qn is an n-cube; and (5) cr(C5¤C5) = 25.