On the Pebbling Numbers of Graphs
Date
2005-05
Authors
Collison, Leighann C.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Graph pebbling is an application which has evolved from the study of graph theory. The goal of pebbling in a graph is to use pebbling steps to move one pebble onto a designated root vertex. A pebbling step is produced by taking two pebbles from a vertex, moving one of them to an adjacent vertex, and throwing out the other pebble. The pebbling number of a graph G, denoted ƒ(G ), is the smallest integer t such that for any distribution of t pebbles on the vertices of G, one pebble can be moved to any specified root vertex.
Within this thesis is an exploration into the origins of basic theorems and properties of the pebbling function. There will be displayed a relationship between a graph’s pebbling number and such characteristics as diameter and number of vertices. Also, new improvements are made to existing upper bounds of this function for specific types of graphs. One such finding is for a complete graph Kn with r missing edges where r ≤ n/2 - 1 the pebbling number is equal to n which categorizes this type of graph as Class 0. Another result is for the Cartesian product of a clique K2 and a graph G the pebbling number has the upper bound of 2ƒ(G ) + n/2 - 1/2. Finally we use the idea of a spanning tree to prove that for any graph G with n vertices and diameter d, there exists an upper bound ƒ(G ) ≤ (2d -1) [n-1/d] + 2n-1-d[n-1/d] which is an improvement of the known upper bound ƒ(G ) ≤ (2d -1)(n - 1) + 1.
Description
Keywords
graph theory, pebbling function
Citation
Collison, L. C. (2005). On the pebbling numbers of graphs (Unpublished thesis). Texas State University-San Marcos, San Marcos, Texas.