2018/04/10 by Czygrinow, Andrzej, Hurlbert, Glenn, Katona, Gyula Y. +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1804.03717
Consider a distribution of pebbles on a connected graph G. A pebbling move removes two pebbles from a vertex and places one to an adjacent vertex. A vertex is reachable under a pebbling distribution if it has a pebble after the application of a sequence of pebbling moves. The optimal pebbling number π^*(G) is the smallest number of pebbles which we can distribute in such a way that each vertex is reachable. It was known that the optimal pebbling number of any connected graph is at most (4n)/(δ+1), where δ is the minimum degree of the graph. We strengthen this bound by showing that equality cannot be attained and that the bound is sharp. If diam(G)≥ 3 then we further improve the bound to π^*(G)≤(3.75n)/(δ+1). On the other hand, we show that for arbitrary large diameter and any ε>0 there are infinitely many graphs whose optimal pebbling number is bigger than ((8)/(3)-ε)(n)/((δ+1)).