On the Pebbling Numbers of Graphs

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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Mathematics

Grantor

Texas State University-San Marcos

Year dc:date.issued

2005

Author dc:creator

• Collison, Leighann C.

Advisor dc:contributor.advisor

• Shen, Jian

Committee members dc:contributor.committeemember

• Ferrero, Daniela
• Jia, Xingde

• graph theory
• pebbling function

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/10877/9616

OAI identifier oai:identifier

oai:digital.library.txst.edu:10877/9616