Pebbling on Directed Graphs

Author(s)

Gayatri Gunda
Aparna Higgins

Document Type

Article

Publication Date

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

Mathematics

eCommons Citation

Gunda, Gayatri and Higgins, Aparna, "Pebbling on Directed Graphs" (2004). Undergraduate Mathematics Day: Past Content. 3.
https://ecommons.udayton.edu/mth_epumd/3