Article

Pebbling on Directed Graphs

Undergraduate Mathematics Day, Electronic Proceedings
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/