Optimally t-Pebbling Graphs
| Autor: | Hung-Hsing Chiang, 姜宏興 |
|---|---|
| Rok vydání: | 2018 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 106 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|