Pebbling on Directed Graphs with Fixed Diameter

MaRDI QIDQ6306401zbMATH OpenFDO

Authors John Asplund, Franklin Kenter

Publication date 7 September 2018

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Pebbling is a game played on a graph. The single player is given a graph and a configuration of pebbles and may make pebbling moves by removing 2 pebbles from one vertex and placing one at an adjacent vertex to eventually have one pebble reach a predetermined vertex. The pebbling number, $pi(G)$, is the minimum number of pebbles such that regardless of their exact configuration, the player can use pebbling moves to have a pebble reach any predetermined vertex. Previous work has related $pi(G)$ to the diameter of $G$. Clarke, Hochberg, and Hurlbert demonstrated that every connected undirected graph on $n$ vertices with diameter 2 has $pi(G)=n$ unless it belongs to an exceptional family of graphs, consisting of those that can be constructed in a specific manner; in which case $pi(G)=n+1$. By generalizing a result of Chan and Godbole, Postle showed that for a graph with diameter $d$, $pi(G)len{2}^{lceilfracd2ceil}(1+o_n(1))$. In this article, we continue this study relating pebbling and diameter with a focus on directed graphs. This leads to some surprising results. First, we show that in an oriented directed graph $G$ (in the sense that if $ioj$ then we cannot have $joi$), it is indeed the case that if $G$ has diameter 2, $pi(G)=n$ or $n+1$, and if $pi(G)=n+1$, the directed graph has a very particular structure. In the case of general directed graphs (that is, if $ioj$, we may or may not have an arc $joi$) with diameter 2, we show that $pi(G)$ can be as large as $frac32n+1$, and further, this bound is sharp. More generally, we show that for general directed graphs, $pi(G)le{2}^{d}n/d+f(d)$ where $f(d)$ is some function of only $d$.

This page was built for publication: Pebbling on Directed Graphs with Fixed Diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6306401)