Skip to main content
Article
Pebbling on Directed Graphs
Undergraduate Mathematics Day, Electronic Proceedings
  • Gayatri Gunda
  • Aparna Higgins
Document Type
Article
Publication Date
1-1-2004
Abstract

Consider a finite connected graph G whose vertices are labeled with non-negative integers representing the number of pebbles on each vertex. A pebbling move on a graph G is defined as the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number f(G) of a connected graph is the least number of pebbles such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified but arbitrary vertex. We consider pebbling on directed graphs and study what configurations of directed graphs allow for pebbling to be meaningful. We also obtain the pebbling numbers of certain orientations of directed wheel graphs Wn with odd order where n > 6 and directed complete graphs Kn with odd order where n > 5. G is said to be demonic if f(G) = n where n is the order of G. We demonstrate the existence of demonic directed graphs and establish that the sharp upper bound and sharp lower bound of the pebbling numbers of the directed graphs is the same as that of the undirected graphs: n < f(G) < 2n − 1.

Disciplines
Citation Information
Gayatri Gunda and Aparna Higgins. "Pebbling on Directed Graphs" (2004)
Available at: http://works.bepress.com/aparna_higgins/1/