On the Pebbling Numbers of Graphs

 dc.contributor.advisor Shen, Jian dc.contributor.author Collison, Leighann C. dc.contributor.committeeMember Ferrero, Daniela dc.contributor.committeeMember Jia, Xingde dc.date.accessioned 2020-04-14T15:52:50Z dc.date.available 2020-04-14T15:52:50Z dc.date.issued 2005-05 dc.description.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. dc.description.department Mathematics dc.format Text dc.format.extent 38 pages dc.format.medium 1 file (.pdf) dc.identifier.citation Collison, L. C. (2005). On the pebbling numbers of graphs (Unpublished thesis). Texas State University-San Marcos, San Marcos, Texas. dc.identifier.uri https://hdl.handle.net/10877/9616 dc.language.iso en dc.subject graph theory dc.subject pebbling function dc.title On the Pebbling Numbers of Graphs dc.type Thesis thesis.degree.department Mathematics thesis.degree.grantor Texas State University-San Marcos thesis.degree.level Masters thesis.degree.name Master of Science

Files

Original bundle

Now showing 1 - 1 of 1