Change search
ReferencesLink to record
Permanent link

Direct link
The Foundations of Graph Pebbling
Stockholm University, Faculty of Science, Department of Mathematics.
2015 (English)Independent thesis Advanced level (degree of Master (One Year)), 240 HE creditsStudent thesis
Abstract [en]

Graph pebbling modeling started as a method for solving a combinatorialnumber theory conjecture by Erdös and Lemke. Using thismethod, Chung proved the conjecture in 1989. Since then, the literaturehas grown considerably. Several variations and possible applicationshave been discussed, in graph theory, computer science andnetwork optimization.

The main focus in graph pebbling is graphs, mathematical structuresmodeling binary relations between vertices. To every vertex insome graph we assign a number of pebbles. If two pebbles are movedacross an edge joining two distinct vertices, one pebble arrives andone pebble is lost. This is called a pebbling step.

The basic question in graph pebbling asks if one may from a givendistribution of pebbles on a set of vertices move to another distributionon the same set via a series of pebbling steps.

In this Master’s thesis we approach the above question using twomodels: a deterministic, which includes the notion of a pebblingnumber, and a probabilistic, which includes the notion of a threshold.

For both these models we clarify earlier proofs, and provide newproofs, of foundational theorems in graph pebbling. These resultsconstitute the backbone for our discussion on recent research, whichconcentrates on generalizing and extending central notions in graphpebbling, for example the generalized idea of a pebbling number:the pi-pebbling function. Simultaneously, a corollary to the so calledcover pebbling theorem is derived. This corollary lets us prove established,and newly found, theorems.

Regarding applications in graph pebbling, we argue that one shouldgeneralize existing results, and incorporate directed graphs into abigger part of the theory. We suggest how this can be done.

Place, publisher, year, edition, pages
2015. , 113 p.
National Category
Other Mathematics
URN: urn:nbn:se:su:diva-128482OAI: diva2:915430

Min handledare, Cecilia Holmgren, var tidigare anställd vid Matematiska institutionen, Stockholms universitet, men arbetar numera vid Matematiska institutionen, Uppsala universitet.

Available from: 2016-11-03 Created: 2016-03-29 Last updated: 2016-11-03Bibliographically approved

Open Access in DiVA

fulltext(3282 kB)11 downloads
File information
File name FULLTEXT01.pdfFile size 3282 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics
Other Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 11 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 62 hits
ReferencesLink to record
Permanent link

Direct link