最優t-圓石分配圖

Optimally t-Pebbling Graphs

姜宏興(Hung-Hsing Chiang)

指導教授 ： 王牧民 ； 史青林

中原大學/理學院/應用數學研究所/博士(2018年)

https://doi.org/10.6840/cycu201800169

摘要

令圖G 是一個簡單圖。一個圖G 的分配是一個函數，它將G 中的每一個點對應到一個非負整數，其中對圖G中的每一個點v， $delta(v)$表示點所分配到的圓石數目。一步圓石移動為將G 中的一個點移除兩顆圓石，然後放一顆圓石到它的鄰點。一個圖G 的分配為t倍可解如果無論選擇哪個目標點v，都可
以使用圓石移動來搬動t 顆圓石到v。圖G的最優t-圓石分配數, 以$pi^*_t (G)$表示，為G中所有t倍可解的分配，使用最少的圓石數目。當t=1時，最優t-圓石分配數就是最優圓石分配數
在這篇論文中，我們主要研究一個圖的最優圓石分配數。在第一章中，我們介紹論文研究的背景知識以及一些基本定義。此外為了讓這篇論文更完整，在第二章中，我們也介紹一些最優圓石分配數和最優t-圓石分配數的已知結果。
第三章中，我們研究環的最優t-圓石分配數，我們所得到的結果為求出$pi^*_2(C_n)$的確切值以及找到t大於或等於3 時$pi^*_t(C_n)$的
上界與下界。而在第四章中，我們以$T^m_h$ 來表示一個高度為h的完整m元樹，然後證明出$pi^*_2(T^2_h ) = pi^* (T^2_{h+1})$ 和$pi^*_4(T^2_h ) = pi^* (T^2_{h+2})$兩個結果。最後我們也求出$pi^*_3(T^2_h)$的3的確切值。在第五章，我們對本篇論文的研究成果做個總結。

關鍵字

最優圓石數 ； 最優t-圓石數 ； 圓圖 ； 完整m樹圖

並列摘要

Let $G$ be a simple graph. A distribution $delta$ of $G$ is a mapping from $V(G)$ into the set of non-negative integers, where $delta(v)$ is the number of pebbles distributed to the vertex $v$ for each $vin V(G)$. A {it pebbling move} consists of removing two pebbles from one vertex and then placing one pebble at an
adjacent vertex. A distribution of a given graph $G$ is $t$-fold solvable if, whenever we choose any target vertex $v$ of $G$, we can move $t$ pebbles on $v$ by using pebbling moves. The optimal $t$-pebbling number of the graph $G$, denoted by $pi^*_{t}(G)$, is the minimum
number of pebbles necessary so that there is a $t$-fold solvable distribution of $G$. When $t=1$, the optimal $t$-pebbling number is the optimal pebbling number.
In this thesis, we mainly study the optimal $t$-pebbling number of a graph. In Chapter $1$, we introduce the background of this study and give some basic definitions. For completeness, we also introduce the known results on the optimal pebbling number and the optimal $t$-pebbling number of a graph in Chapter $2$. In Chapter $3$, we study the optimal $t$-pebbling number of the cycle. As a consequence, we determine the exact value of $pi^*_{2}(C_{n})$ for each cycle $C_n$. We then derive an upper bound and a lower bound for $pi^*_{t}(C_{n})$ for $tgeq 3$. In Chapter $4$, let $T^m_h$ denote the complete $m$-ary tree with height $h$, we first show that $$pi^{ast}_{2}(T^2_{h})=pi^{ast}(T^2_{h+1})qquad ext{and} qquad
pi^{ast}_{4}(T^2_{h})=pi^{ast}(T^2_{h+2})$$ and then determine the exact value of $pi^{ast}_{3}(T^2_{h})$. In Chapter $5$, we conclude our research results in this thesis.

並列關鍵字

pebbling ； optimal pebbling numbers ； optimal t-pebbling numbers ； cycle ； complete m-ary tree

參考文獻

1. H. J. Bandelt, Retracts of hypercubes, Journal of Graph Theory. Volume 8, lssue 4 (1984), 501--510.

2.D. P. Bunde, E. W. Chambers, D. Cranston, K. Milans and D. B. West, Pebbling and optimal pebbling in graphs, J. Graph Theory 57 (2008), 215--238.

3. G. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theoryr, Mc Graw-Hill (1993), 419--429.

4. F. R. K. Chung, Pebbling in hypercubes, SIAM J. Discrete Math. 2(1989), 467--472.

5. T. A. Clarke, R. A. Hochberg and G. H. Hurlbert, Pebbling in diameter two graphs and products of paths, J. Graph Theory 25 (1997), 119--128.